Editing NP (complexity) (section)

=== NP-complete problems ===

{{main|List of NP-complete problems}}

Every [[NP-completeness|NP-complete]] problem is in NP.

==== Boolean satisfiability ====

The [[Boolean satisfiability problem]] ('''SAT'''), where we want to know whether or not a certain formula in [[propositional logic]] with [[Boolean variable]]s is true for some value of the variables.<ref>{{Cite book|last=Karp|first=Richard|title=Complexity of Computer Computations |chapter=Reducibility among Combinatorial Problems |date=1972|chapter-url=http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf|pages=85–103 |doi=10.1007/978-1-4684-2001-2_9 |isbn=978-1-4684-2003-6 }}</ref>

==== Travelling salesman ====

The decision version of the [[travelling salesman problem]] is in NP. Given an input matrix of distances between ''n'' cities, the problem is to determine if there is a route visiting all cities with total distance less than ''k''.

A proof can simply be a list of the cities. Then verification can clearly be done in polynomial time. It simply adds the matrix entries corresponding to the paths between the cities.

A [[nondeterministic Turing machine]] can find such a route as follows:

* At each city it visits it will "guess" the next city to visit, until it has visited every vertex. If it gets stuck, it stops immediately.
* At the end it verifies that the route it has taken has cost less than ''k'' in ''[[Big-O notation|O]]''(''n'') time.

One can think of each guess as "[[fork (system call)|forking]]" a new copy of the Turing machine to follow each of the possible paths forward, and if at least one machine finds a route of distance less than ''k'', that machine accepts the input. (Equivalently, this can be thought of as a single Turing machine that always guesses correctly)

A [[binary search]] on the range of possible distances can convert the decision version of Traveling Salesman to the optimization version, by calling the decision version repeatedly (a polynomial number of times).<ref>{{Cite web|last=Aaronson|first=Scott|title=P=? NP|url=https://www.scottaaronson.com/papers/pnp.pdf|access-date=13 Apr 2021}}</ref><ref name=":0">{{Cite web|last=Wigderson|first=Avi|title=P, NP and mathematics – a computational complexity perspective|url=https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf|access-date=13 Apr 2021}}</ref>

==== Subgraph isomorphism ====

The [[subgraph isomorphism problem]] of determining whether graph {{mvar|G}} contains a subgraph that is isomorphic to graph {{mvar|H}}.<ref>{{Cite book|last1=Garey|first1=Michael R.|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|last2=Johnson|first2=David S.|publisher=W.H. Freeman|year=1979|isbn=0-7167-1045-5}}</ref>