NP is the class of languages such that there exists a nondeterministic TM that accepts that language in polynomial time.
An alternative definition is to say NP is the class of languages that can be efficiently certified. So, if , then there exists a polynomial sized, in , certificate that can prove .
A few examples…
- Clique: Does there exist a clique of size in a graph ?
- The certificate is the subset of vertices that are in the clique, and then the verifier will check if there is an edge between every pair of vertices.
- Independent Set: Does there exist an independent set of size in a graph ?
- As with clique, verifier takes a set of vertices with size and check if every pair of vertices have no edge.
- Hamiltonian Cycle: Does there exists a Hamiltonian cycle (a cycle of length , using each vertex exactly once) in ?
- Vertex Cover: Does there exist a vertex cover of size in ?
- Recall a vertex cover is a set of vertices such that each edge has at least one of its endpoints in the set.
- TSP: Does there exist a tour in that visits every vertex and returns to the origin, and has length ?
- Integer Linear Programming (ILP): Given , does there exist an such that ?
- The certificate is the vector . We check if and that is all integers.
- SAT: Given a satisfiability instance , does there exist a boolean assignment such that is true?
These are just a few of the problems that are in NP. All of the problems given above do not currently have a polynomial time algorithm. Can we come up with one? Is there anything that prevents us from coming up with a polynomial time algorithm?
Which problem seems the easiest to develop a poly-time algorithm? It turns out they are equally difficult–a polynomial time algorithm for any of them would give a polynomial time algorithm for all of them. To understand this, we introduce the notion of reduction.
We say a decision problem is reducible to a decision problem if there exists an algorithm to solve using a procedure to solve .
is a polytime reduction, on input of size , if the algorithm makes only a poly number of calls to , each on inputs of size poly, and uses poly additional time. We use to say is polytime reducible to .
CLIQUE INDEPENDENT-SET? Given an instance of CLIQUE, we call the algorithm for INDEPENDENT-SET on the complement of this graph, . Then, an independent set in of size will be a clique of size . There is a nearly equivalent reduction from INDEPENDENT-SET CLIQUE.
Given an instance of VERTEX-COVER, call INDEPENDENT-SET on this graph. Call the independent set it finds . Then, take the complement of this , which will be a vertex cover. The following claim shows how to use the reduction to answer the decision question:
Claim: has a vertex cover of size iff has an independent set of size .
Given an instance of SAT, write each clause as an equation. For example, a clause become an equation . We then add bounds to enforce each is either or .
Definition A language is NP-complete if
- For all NP, there exists a polytime reduction .
So if is NP-complete, is the “hardest” language in NP. Also if is NP-complete and , then and .
But does there exist an NP-complete language? We show first that SAT is NP-complete.
Theorem (Cook-Levin). SAT is NP-complete.
Proof: We need to show that for all , that we can decide given a procedure to decide SAT.
Suppose . Then, there exists a NTM that accepts any in steps for some fixed . This also implies that there exists a sequence of configurations from a starting configuration to if . We will show how to check the existence of such an accepting path as a polynomial-sized SAT formula.
We encode the steps of computation of by transforming the state of the NTM into literals. Define
Note that and that for all for exactly one value of . We can encode the requirement of exactly one literal being true as a SAT instance. For two literals and a clause , the following requires that exactly one of the literals be true:
More generally, for literals and a clause , the following evaluates to true if and only if the original clause has exactly one literal set to true:
We encode the existence of an accepting path in the NTM as the following SAT instance:
- For each pair create a set of clauses
- Encode the input/initial configuration as .
- Require that we reach an accept state somewhere: .
- Ensure that every transition is valid by requiring that the current state leads to a valid future state. We consider windows of three symbols at both the current/next step, because a TM can read/write and move either L/R in a single transition. The we consider 6 literals at a time for a window and then ensure that every window is valid:
We then concatenate all the clauses from 1-4 above into a single function , where has a satisfying assignment iff the original input . The size of the formula is at most .