NP-completeness

M. Garey, D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness] W.H. Freeman, New York, 1979. 

Just as there are universal computers that, given a particular input, can simulate any other com-puter, there are NP-complete problems that, with the appropriate input, are effectively equivalent to any NP-hard problem of a given size. For example, Boolean satisfiability -i.e. the problem of determining truth values of the variable s of a Boolean expression so that the expression is true -is known to be an NP-complete problem. See section 12.3.5.2... 

At this point the lower-bounding scheme consists of solving a single machine scheduling problem where for each job i, the release time is the due date is, and the processing time is This nonbottleneck scheme can be further simplified in two steps. First, we can assume that for a/8 =. ., avoiding the need to consider release times of and due dates of, which turns an NP-complete problem, into one solvable in polynomial time. If only one of these were to be relaxed, the schedule can still be foimd in polynomial time by Jackson s rule (Jackson, 1955). Second, we can avoid the computation of completely, by assuming that the maximum is obtained at / = m for all values of i. 

In further work, the achievement of well-controlled reaction conditions in micro reactors is highlighted to provide chemical data yielding a highly parallel system of problem-solving fimctions [131]. This is used to approach a class of problems in computer science that is called NP-complete, for which algorithms are very difficult to solve. In summary, this mathematical approach is used to describe chemical reactions which are highly parallel systems as the parameter space and the related dependencies are virtually infinite (Figure 4.80). 

Lathrop, R. FI. (1994). The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein Eng. 7, 1059—1068. 

K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Math. Progr., 39 117,1987. 

Once these ontological specifications are created, it is possible to apply reasoning tools to automatically create workflows of services that tackle tasks that require the involvement of multiple services. These are of particular interest, as they offer the possibility of on-the-fly aggregation of services and information in response to a scientist s (potentially complex) query, without the need for workflows to have been predefined. Such reasoning tools already exist, but they require exhaustive search of the Web services space (an NP-complete problem). Techniques and heuristics are being developed in the Semantic Web community to reduce the search spaces and effect efficient searches. We will participate in these efforts while tailoring the searches to cheminformatics. 

The above example is convenient for illustration because it is relatively small and involves only uni-unimolecular reactions. For large systems with arbitrary reaction stoichiometry, it turns out that the assignment of feasible reactions is an NP-complete computational problem [216], Therefore, application of thermodynamic constraints in genome-scale problems is an area of ongoing research. 

If a linear hexapeptide solution existed, it must have been present in Geysen s library (provided the synthesis worked perfectly, which is a separate issue). There are no additional umepresented sequences, and mathematically such libraries are called NP-complete (NP = non-deterministic polynomial time). Such NP-complete libraries are actually quite rare in combinatorial chemistry. Although there are infinite numbers of peptides, for Geysen s epitope mapping, he needed to examine only natural amino acids. This reduces the complexity for a sequence of length n to 20", a number that increases exponentially with n but nevertheless remains finite. 

Among peptide libraries today, such NP-complete sets are uncommon. It is often profitable to expand the monomer set to include unnatmal amino acids, thus once again leading to infinite possibilities. Even within the narrower context of natural peptides, the complete set of 20 amino acids is seldom employed in synthetic libraries. In Houghten s example above, both cysteine and tryptophan were omitted to avoid problems due to oxidative side reactions, while others often substitute... 

We chose the above problem merely to evaluate the potential of SA for the batch process scheduling problems. It was an obvious choice, because it has been studied extensively (Ku et al. 1987) in the literature, thus algorithms for comparison already exist in the literature. This problem of finding a sequence with minimum total time (called makespan) to produce all N batches has been shown to be NP-complete for M>2 by Garey et al. (1976), thus no polynomialtime algorithms exist for getting optimal solutions. We now describe our implementation of the SA algorithm. 

EvYa80 Shimon Even, Yacov Yacobi Cryptocomplexity and NP-Completeness 7th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 85, Springer-Verlag, Heidelberg 1980,195-207. 

Due to the nature of this approach, subgraph isomorphism algorithms are time consuming isomorphism is a combinatorial problem belonging to the nondetermin-istic polynomial time complete (NP complete) class of problems, which are widely believed to be unsolvable. Several authors suggested improvements to reduce the... 

The involved alignment optimization problem, i.e. the problem of finding a sequence-structure alignment with minimum pair interaction score is NP-complete [38],... 

---