![]() | This
user page is actively undergoing a
major edit for a short while. To help avoid
edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 13:22, 9 January 2022 (UTC) (2 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{ Under construction}} between editing sessions. |
![]() | This article may be
confusing or unclear to readers. (July 2012) |
In computational complexity theory, a problem is NP-complete if it is in NP, and it is NP-hard. Informally, a problem is in NP if there exist an efficient algorithm, a polynomial time algorithm, that can verify the solution to this problem. It is NP-hard if every problem in NP can be reduced to it in polynomial time. In other, NP-hard problem is at least as hard as the hardest problem in NP. A problem that is NP-Hard does not necessary belongs to NP.
The name "NP-complete" is abbreviation for "Nondeterministic Polynomial-time Complete". In this name, "Nondeterministic Polynomial-time" refers to the complexity class of Decision problems that can be decided in polynomial number of steps using nondeterministic Turing machines, a Turing machine that have an nondeterministic transition function. " Complete" refers to the property of being able to simulate every problem in a given complexity class.
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 "efficiently", there is no known algorithm till now that decides NP-Complete problems efficiently. That is, the Time complexity required to decide the problem by any currently known algorithm, so far, increases rapidly as the size of the problem grows.
Knowing if an efficient algorithm exists to decide NP-Complete problem is a major unsolved problems in computer science, called the P versus NP problem. Since NP-complete problems are very common and frequent in several fields, several coping mechanism and algorithm techniques has been developed such the using heuristic methods, approximation algorithms, and Fixed-parameter algorithms.
We define a language as subset of binary strings from all possible binary string combinations. We say a language is in NP if there exist a polynomial time Turing machine that takes two binary strings, usually called the verifier of , such for every binary string ,
is a polynomial in size of , and is called the certificate for with respect to the language and machine
Given two languages , we say is a Karp Polynomial-time reducible to , If there exists a polynomial-time computable function such that if then We denote this fact by .
A language is NP-hard if for every , we have . A language is NP-complete if it is NP-hard and .
The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem), though the term NP-complete was introduced later. At the 1971 STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other. This is known as "the question of whether P=NP".
Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US$1 million reward to anyone who has a formal proof that P=NP or that P≠NP.
The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness. [2]
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:
The Sub-graph 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. These are called NP-Intermediate problems and exist if and only if P≠NP.
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. The list below contains some well-known problems that are NP-complete when expressed as decision problems.
To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. 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.
There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, NL-complete), and the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs. Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.
At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, in fact exponential in [ clarify] 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.
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. [3] It is known, however, that AC0 reductions define a strictly smaller class than polynomial-time reductions. [4]
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. [5] Other suggestions made in the poll [6] 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". [7]
The following misconceptions are frequent. [8]
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 whether NP=co-NP is an open question. [11]
The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.
Category:1971 in computing
Category:Complexity classes
Category:Mathematical optimization
![]() | This
user page is actively undergoing a
major edit for a short while. To help avoid
edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 13:22, 9 January 2022 (UTC) (2 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{ Under construction}} between editing sessions. |
![]() | This article may be
confusing or unclear to readers. (July 2012) |
In computational complexity theory, a problem is NP-complete if it is in NP, and it is NP-hard. Informally, a problem is in NP if there exist an efficient algorithm, a polynomial time algorithm, that can verify the solution to this problem. It is NP-hard if every problem in NP can be reduced to it in polynomial time. In other, NP-hard problem is at least as hard as the hardest problem in NP. A problem that is NP-Hard does not necessary belongs to NP.
The name "NP-complete" is abbreviation for "Nondeterministic Polynomial-time Complete". In this name, "Nondeterministic Polynomial-time" refers to the complexity class of Decision problems that can be decided in polynomial number of steps using nondeterministic Turing machines, a Turing machine that have an nondeterministic transition function. " Complete" refers to the property of being able to simulate every problem in a given complexity class.
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 "efficiently", there is no known algorithm till now that decides NP-Complete problems efficiently. That is, the Time complexity required to decide the problem by any currently known algorithm, so far, increases rapidly as the size of the problem grows.
Knowing if an efficient algorithm exists to decide NP-Complete problem is a major unsolved problems in computer science, called the P versus NP problem. Since NP-complete problems are very common and frequent in several fields, several coping mechanism and algorithm techniques has been developed such the using heuristic methods, approximation algorithms, and Fixed-parameter algorithms.
We define a language as subset of binary strings from all possible binary string combinations. We say a language is in NP if there exist a polynomial time Turing machine that takes two binary strings, usually called the verifier of , such for every binary string ,
is a polynomial in size of , and is called the certificate for with respect to the language and machine
Given two languages , we say is a Karp Polynomial-time reducible to , If there exists a polynomial-time computable function such that if then We denote this fact by .
A language is NP-hard if for every , we have . A language is NP-complete if it is NP-hard and .
The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem), though the term NP-complete was introduced later. At the 1971 STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other. This is known as "the question of whether P=NP".
Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US$1 million reward to anyone who has a formal proof that P=NP or that P≠NP.
The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness. [2]
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:
The Sub-graph 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. These are called NP-Intermediate problems and exist if and only if P≠NP.
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. The list below contains some well-known problems that are NP-complete when expressed as decision problems.
To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. 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.
There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, NL-complete), and the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs. Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.
At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, in fact exponential in [ clarify] 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.
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. [3] It is known, however, that AC0 reductions define a strictly smaller class than polynomial-time reductions. [4]
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. [5] Other suggestions made in the poll [6] 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". [7]
The following misconceptions are frequent. [8]
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 whether NP=co-NP is an open question. [11]
The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.
Category:1971 in computing
Category:Complexity classes
Category:Mathematical optimization