Editing P versus NP problem (section)

==NP-completeness==
[[File:P np np-complete np-hard.svg|thumb|300px|right|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)]]
{{Main article|NP-completeness}}
To attack the P&nbsp;=&nbsp;NP question, the concept of NP-completeness is very useful. NP-complete problems are problems that any other NP problem is reducible to in polynomial time and whose solution is still verifiable in polynomial time. That is, any NP problem can be transformed into any NP-complete problem. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.

[[NP-hard]] problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time.

For instance, the [[Boolean satisfiability problem]] is NP-complete by the [[Cook–Levin theorem]], so ''any'' instance of ''any'' problem in NP can be transformed mechanically into a Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many NP-complete problems. If any NP-complete problem is in P, then it would follow that P&nbsp;=&nbsp;NP. However, many important problems are NP-complete, and no fast algorithm for any of them is known.

From the definition alone it is unintuitive that NP-complete problems exist; however, a trivial NP-complete problem can be formulated as follows: given a [[Turing machine]] ''M'' guaranteed to halt in polynomial time, does a polynomial-size input that ''M'' will accept exist?<ref name="Scott">{{Cite web|author=Scott Aaronson|title=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html |access-date=27 August 2007}}</ref> It is in NP because (given an input) it is simple to check whether ''M'' accepts the input by simulating ''M''; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine ''M'' that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713&ndash;717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability. So a polynomial-time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time. Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".