NP-hard

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... 

Problem-1 is a formidable challenge for mathematical programming. It is an NP-hard problem, and consequently all computational attempts to solve it cannot be guaranteed to provide a solution in polynomial time. It is not surprising then that all previous efforts have dealt with simplified versions of Problem-1. These simplifications have led to a variety of... 

Section III introduces the concept of nonmonotonic planning and outlines its basic features. It is shown that the tractability of nonmonotonic planning is directly related to the form of the operators employed simple propositional operators lead to polynomial-time algorithms, whereas conditional and functional operators lead to NP-hard formulations. In addition, three specific subsections establish the theoretical foundation for the conversion of operational constraints on the plans into temporal orderings of primitive operations. The three classes of constraints considered are (1) temporal ordering of abstract operations, (2) avoidable mixtures of chemical species, and (3) quantitative bounding constraints on the state of processing systems. 

Theorem 3 (First Intractability Theorem). The problem of determining whether a proposition is necessarily true in a nonmonotonic plan whose action representation is sufficiently strong to represent conditional actions is NP-hard. 

The simplest formulation of the packing problem is to give some collection of distance constraints and to calculate these coordinates in ordinary three-dimensional Euclidean space for the atoms of a molecule. This embedding problem - the Fundamental Problem of Distance Geometry - has been proven to be NP-hard [116]. However, this does not mean that practical algorithms for its solution do not exist [117-119]. 

Unger, R. and Moult, J. (1993) Finding the lowest free energy conformation of a protein is a NP-hard problem proof and implications, Bull. Math. Biol., 55, 1183-1198. 

Despite advances in MILP solution methods, problem size is still a major issue since scheduling problems are known to be NP-hard (i.e., exponential increase of computation time with size in worst case). While effective modeling can help to overcome to some extent the issue of computational efficiency, special solution strategies such as decomposition and aggregation are needed in order to address the ever increasing sizes of real-world problems. 

P. M. Pardalos and G. Schnitger. Checking local optimality in constrained quadratic programming is NP-Hard. Oper. Res. Lett., 7(1) 33,1988. 

P. M. Pardalos and S. A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim., 1 15,1991. 

The concept of biclustering has emerged in the context of microarray experiments since a gene can be involved in more than one biological process or could be co-expressed with other genes for only a subset of the conditions. Several existing approaches use heuristic methods, discretize the expression level, and/or solve a simplified model to address this NP-hard problem [6]. An excellent review of several biclustering methods can be found in [7]. 

The internal clustering criterion allows us to formulate clustering as an optimization problem. Unfortunately, this optimization problem falls into the category of NP-hard making it intractable for all but the smallest problem instances. Hence, a number of heuristic approaches have been advocated and in many cases these approaches do not explicitly specify the internal criterion being optimized. 

The simulation of frustrated systems suffers from a similar tunneling problem as the simulation of first order phase transitions local minima in energy space are separated by barriers that grow with system size. While the multicanonical or optimized ensembles do not help with the NP-hard problems faced by spin glasses, they are efEcient in speeding up simulations of frustrated magnets without disorder. 

The rectangle cover problem is known to be NP-hard and approximation algorithms with small performance ratios for this problem are unknown ([6,7]). We explore the specifics of oligonucleotide masks and devise an efficient algorithm which finds a (provably) optimal rectangle cover for all masks we tested at Affymetrix. 

---