NP-completeness

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

puzzle, but once a solution has been found its validity can be verified easily. It is NP-complete to determine whether an Sudoku has a valid solution. In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". # Each input to the problem is associated with a collection of short (polynomial size) solutions, which might or might not validly solve the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them is. # The validity of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a valid solution (if one exists) by trying all possible solutions. # The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid solutions of some NP-complete problem quickly (when they exist), we could quickly find valid solutions for every other problem in which a given solution can be easily verified. Problems that meet the first three criteria belong to the class NP, which is short for "nondeterministic polynomial-time".…

puzzle, but once a solution has been found its validity can be verified easily. It is NP-complete to determine whether an Sudoku has a valid solution. ]] In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". Each input to the problem is associated with a collection of short (polynomial size) solutions, which might or might not validly solve the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them is. The validity of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a valid solution (if one exists) by trying all possible solutions. The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid solutions of some NP-complete problem quickly (when they exist), we could quickly find valid solutions for every other problem in which a given solution can be easily verified. Problems that meet the first three criteria belong to the class NP, which is short for "nondeterministic polynomial-time". 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. A problem that is in NP and also meets the fourth criterion is said to be "NP-complete". The term "complete" refers to the property of being able to simulate everything in the same complexity class: 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. for P, NP, NP-complete, and NP-hard sets of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete, and in general, not every problem in P or NP is NP-complete).]] A decision problem \scriptstyle C is NP-complete if: \scriptstyle C is in NP, and Every problem in NP is reducible to \scriptstyle C in polynomial time. \scriptstyle C can be shown to be in NP by demonstrating that a candidate solution to \scriptstyle C can be verified in polynomial time. A decision problem that is solvable in polynomial time belongs to the class P. All problems in P are necessarily in NP. However, it has not been proved that the class NP is actually larger than P. In other words, it is not yet known whether there exist problems in NP that are not in P. The question of whether the classes P and NP are equal or not is known as the P versus NP problem. A consequence of the definition of NP-completeness is that if we had a polynomial-time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for \scriptstyle C , we could solve all problems in NP in 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 are thus, in a sense, the hardest problems in NP.

Intermediate problems

An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. Consider these two problems: Graph Isomorphism: Is graph G 1 isomorphic to graph G 2 ? Subgraph Isomorphism: Is graph G 1 isomorphic to a subgraph of graph G 2 ? The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but is not thought to be NP-complete. This class is called NP-Intermediate problems and exists if and only if P≠NP. "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. "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, information-theoretic security provides cryptographic methods that cannot be broken even with unlimited computing power. "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. 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. P = NP problem Strongly NP-complete Travelling Salesman (2012 film)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375967366 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.