P = the class of languages for which membership can be decided quickly
NP = the class of languages for which membership can be verified quickly
"The question of whether P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics."
A = {w | V accepts <w, c> for some string c}
The string c is called the certificate (aka proof) of w.
Essentially, c represents the solution for input w
Example: for HAMPATH, the certificate for <G, s, t> would be the path itself.
Example: COMPOSITES = {x | x = pq for naturals p and q}
Def. 7.19: NP is the class of langauges that have polynomial time verifiers
In other words, languages in NP can be verified quickly
HAMPATH ∈ NP
COMPOSITES ∈ NP
P ⊆ Turing Decidable
Question: Is there a language L such that
To answer, one must show that L has NO polynomial time algorithm to decide it
No one knows how to prove this negative, so ...
We do something easier: Analyze languages that have no known decider but that have a known verifier (both of polynomial time, of course)
Theorem 7.27: SAT ∈ P iff P = NP
Let me say it again: SAT ∈ P iff P = NP
A Boolean expression φ is satisfiable iff some assignment of 0's and 1's to its variables makes it true.
Examples:
φ = x ∧ y is satisfiable
φ = x ∧ x' is not satisfiable
φ = (x' ∧ y) ∨ (x ∧ z') is satisfiable
SAT = {<φ> | φ is a satisfiable Boolean expression}
A language B is NP-complete if it satisfies two conditions:
B is in NP, and
every A in NP is polynomial time reducible to B
w ∈ A ⇔ f(w) ∈ B
In other words: An input to A can be transformed into an input to B.
To decide whether w is in A, simply test if f(w) is in B!
Polynomial time reducible means that f is a polynomial time function.
Theorem 7.35: If B is NP-complete and B ∈ P, then P = NP.
Proof follows directly from definition of polynomial time reducibility.
Theorem 7.37: SAT is NP-complete
Proof of 1: Easy to show SAT ∈ NP
Proof of 2: Show every problem A in NP can be reduced to SAT!
Theorem 7.30: A language isin NP iff it is decided by some nondeterministic polynomial time Turing Machine.
Proof: Use a verifier to construct a decider, and vice versa
CLIQUE = {<G, k> | G is an undirected graph with a k-clique}
3SAT = {<φ> φ is a satisfiable 3cnf formula}
A 3cnf formula has three variables and is made up of ANDS of OR terms
CLIQUE and 3SAT are both NP-complete