NP completeness

Among the hundreds of problems known to be NP-complete are:

• Can a non-deterministic 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², 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 NP-complete 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 NP-complete but the other is in P. Examples include:

• Finding a Hamiltonian circuit that visits once every node in a given network is NP-complete, but finding an Euler circuit that visits once every connection is in P.

• Finding the longest path between two nodes in a network is NP-complete, but finding the shortest path is in P.

• Determining satisfiability for a Boolean expression with 3 variables in each clause is NP-complete, 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² + b y  c is NP-complete, 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 NP-complete, but is in P if there is no magnetic field.

• Finding the permanent of a matrix is NP-complete, 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 NP-complete. It is known that in principle there exist NP problems that are not in P, yet are not NP-complete.