NP completeness Among the hundreds of problems known to be NPcomplete are: • Can a nondeterministic Turing machine reach a certain state in a given number of steps? • Can a multiway system generate a certain string in a given number of steps? • Is there an assignment of truth values to variables that makes a given Boolean expression true? (Satisfiability; related to minimal Boolean expressions of page 1095.) • Will a given sequence of pair comparisons correctly sort any list (see page 1142)? • Will a given pattern of origami folds yield an object that can be made flat? • Does a network have any parts that match a given subnetwork (see page 1038)? • Is there a path shorter than some given length that visits all of some set of points in the plane? (Travelling salesman; related to the network layout problem of page 1031.) • Is there a solution of a certain size to an integer linear programming problem? • Is there any x < a such that Mod[x^^{2}, b] == c? (See page 1090.) • Does a matrix have a permanent of given value? • Is there a way to satisfy tiling constraints in a finite region? (See page 984.) • Is there a string of some limited length that solves a correspondence problem? • Is there an initial condition to a cellular automaton that yields particular behavior after a given number of steps? (In cases where numbers are involved, it is usually crucial that these be represented by base 2 digit sequences, and not, say, in unary.) Many NPcomplete problems at first seem quite unrelated. But often their equivalence becomes clear just by straightforward identification of terms. And so for example the equivalence of satisfiability to problems about networks can be seen by identifying variables and clauses in Boolean expressions respectively with connections and nodes in networks. One can get an idea of the threshold of NP completeness by looking at seemingly similar problems where one is NPcomplete but the other is in P. Examples include: • Finding a Hamiltonian circuit that visits once every node in a given network is NPcomplete, but finding an Euler circuit that visits once every connection is in P. • Finding the longest path between two nodes in a network is NPcomplete, but finding the shortest path is in P. • Determining satisfiability for a Boolean expression with 3 variables in each clause is NPcomplete, but for one with 2 variables is in P. (The latter is like a network with only 2 connections at each node.) • Solving quadratic Diophantine equations a x^^{2} + b y == c is NPcomplete, but solving linear ones a x + b y == c is in P. • Finding a minimum energy configuration for a 2D Ising spin glass in a magnetic field is NPcomplete, but is in P if there is no magnetic field. • Finding the permanent of a matrix is NPcomplete, but finding its determinant is in P. It is not known whether problems such as integer factoring or equivalence of networks under relabelling of nodes (graph isomorphism) are NPcomplete. It is known that in principle there exist NP problems that are not in P, yet are not NPcomplete.
