3 Example problems

An interesting example is the problem, in graph theoryGraph theory is the branch of mathematics that examines the properties of graphs . A graph with 6 vertices and 7 edges. Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs). Typically, a graph is dep, of graph isomorphismIn mathematics, an isomorphism is a kind of interesting mapping between objects. Douglas Hofstadter provides an informal definition: :The word "isomorphism" applies when two complex structures can be mapped onto each other, in such a way that to each part. Two graphs are isomorphic if one can be transformed into the other simply by renaming verticesIn geometry, a vertex ( Latin: whirl, whirlpool; plural vertices is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). In graph theory, a graph describes a set of connections betw. Consider these two problems:

Graph Isomorphism: Is graph G₁ isomorphic to graph G₂? Subgraph Isomorphism: Is graph G₁ isomorphic to a subgraph of graph G₂?

The Subgraph Isomorphism problem is NP-complete. The Graph Isomorphism problem is suspected to be neither in P nor NP-complete, though it is obviously in NP. This is an example of a problem that is thought to be hard, but isn't thought to be NP-complete.

The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. Here are a few:

• Boolean satisfiability problem (SAT)
• Fifteen puzzle
• Knapsack problemThe knapsack problem is a problem in combinatorics, complexity theory, cryptography, and applied mathematics. Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less t
• Hamiltonian cycle problem
• Traveling salesman problem
• Subgraph isomorphism problem
• Subset sum problem
• Clique problem
• Vertex cover problem
• Independent Set problem

Here is a diagram of some of the NP-Complete problems and the reductions typically used to prove their NP-completeness. In this diagram, an arrow from one problem to another indicates the direction of the reduction. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.

4 Alternative approaches

In the definition of NP-complete given above, the term "reduction" was used in the technical meaning of polynomial-time many-one reduction.

Another type of reduction is polynomial-time Turing reduction. A problem X is polynomial-time Turing-reducible to a problem Y if, given a subroutine that solves Y in polynomial time, you could write a program that calls this subroutine and solves X in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program.

If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger. If the two concepts were the same, then it would follow that NP = Co-NP. This holds because by their definition the classes of NP-complete and co-NP-complete problems under Turing reductions are the same and because these classes are both supersets of the same classes defined with many-one reductions. So if both definitions of NP-completeness are equal then there is a co-NP-complete problem (under both definitions) such as for example the complement of the boolean satisfiability problem that is also NP-complete (under both definitions). This implies that NP = co-NP as is shown in the proof in the article on co-NP. Although the question of NP = co-NP is an open question it is considered unlikely and therefore it is also unlikely that the two definitions of NP-completeness are equivalent.

Another type of reduction that is also often used to define NP-completness is the logarithmic-space many-one reduction which is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as P-complete. Whether under these types of reductions the definition of NP-complete changes is still an open problem.

5 References

• Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. BooksEnthsiast.com (This book is a classic, developing the theory, then cataloging many NP-Complete problems)
• S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151-158
• Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems. KTH NADA. Stockholm.
• Computational Complexity of Games and Puzzles
• Tetris is Hard, Even to Approximate
• Minesweeper is NP-complete!

Important complexity classes ( more)

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

Complexity classes

<Hide>