Katana VentraIP

NP-completeness

In computational complexity theory, a problem is NP-complete when:

The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the same complexity class.


More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in polynomial time),[2] such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.


Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today.


While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.

Overview[edit]

NP-complete problems are in NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine. A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.


It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem. But if any NP-complete problem can be solved quickly, then every problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general.

Graph Isomorphism: Is graph G1 isomorphic to graph G2?

Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?

: Instead of searching for an optimal solution, search for a solution that is at most a factor from an optimal one.

Approximation

: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. Note: The Monte Carlo method is not an example of an efficient algorithm in this specific sense, although evolutionary approaches like Genetic algorithms may be.

Randomization

Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.

: Often there are fast algorithms if certain parameters of the input are fixed.

Parameterization

: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.

Heuristic

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size. The vertex cover problem has [6] for some and it is unknown whether there are any faster algorithms.


The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:


One example of a heuristic algorithm is a suboptimal greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.

Completeness under different types of reduction[edit]

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


Another type of reduction is polynomial-time Turing reduction. A problem is polynomial-time Turing-reducible to a problem if, given a subroutine that solves in polynomial time, one could write a program that calls this subroutine and solves 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.


Another type of reduction that is also often used to define NP-completeness 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. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as reductions and reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections.[7] It is known, however, that AC0 reductions define a strictly smaller class than polynomial-time reductions.[8]

Naming[edit]

According to Donald Knuth, the name "NP-complete" was popularized by Alfred Aho, John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the theoretical computer science community.[9] Other suggestions made in the poll[10] included "Herculean", "formidable", Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time".[11]

"NP-complete problems are the most difficult known problems." Since NP-complete problems are in NP, their running time is at most exponential. However, some problems have been proven to require more time, for example . Of some problems, it has even been proven that they can never be solved at all, for example the halting problem.

Presburger arithmetic

"NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example ). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see Valiant–Vazirani theorem).

minimum spanning tree

"Solving NP-complete problems requires exponential time." First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time such as O(2√nn). For example, the and dominating set problems for planar graphs are NP-complete, but can be solved in subexponential time using the planar separator theorem.[13]

independent set

"Each instance of an NP-complete problem is difficult." Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.

[14]

"If P=NP, all cryptographic ciphers can be broken." A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. In addition, provides cryptographic methods that cannot be broken even with unlimited computing power.

information-theoretic security

"A large-scale quantum computer would be able to efficiently solve NP-complete problems." The class of decision problems that can be efficiently solved (in principle) by a fault-tolerant quantum computer is known as BQP. However, BQP is not believed to contain all of NP, and if it does not, then it cannot contain any NP-complete problem.

[15]

The following misconceptions are frequent.[12]

union

intersection

concatenation

Kleene star

Viewing a decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under:


It is not known whether NPC is closed under complementation, since NPC=co-NPC if and only if NP=co-NP, and since NP=co-NP is an open question.[16]

Almost complete

Gadget (computer science)

Ladner's theorem

List of NP-complete problems

NP-hard

P = NP problem

Strongly NP-complete

Travelling Salesman (2012 film)