Section 7-3-5: P=NP? and NP-Complete

# Section 7-3-5: P=NP? and NP-Complete

### P = NP: The Great Unsolved Problem

• 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."

### Verification

• Def. 7.18: A verifier for a language A is an algorithm V, where

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}

• Certificate is p or q

### The Class NP

• Def. 7.19: NP is the class of langauges that have polynomial time verifiers

• In other words, languages in NP can be verified quickly

• Given an input and its certificate we can verify in polynomial time that the input is in the language
• HAMPATH ∈ NP

• COMPOSITES ∈ NP

### Why we Care about NP

• Turing Decidable (TD) ⊂ Turing Recognizable ⊂ All Languages
• Proper subsets
• P ⊆ Turing Decidable

• Question: Is there a language L such that

• L ∈ TD
• L ∉ P
• 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)

### Cook-Levin Theorem

• Theorem 7.27: SAT ∈ P iff P = NP

• Let me say it again: SAT ∈ P iff P = NP

### SAT: Satisfiability Theorem

• A Boolean expression φ is satisfiable iff some assignment of 0's and 1's to its variables makes it true.

• Examples:

• φ = xy is satisfiable

• φ = xx' is not satisfiable

• φ = (x'y) ∨ (xz') is satisfiable

• SAT = {<φ> | φ is a satisfiable Boolean expression}

### NP-Complete Languages

• A language B is NP-complete if it satisfies two conditions:

1. B is in NP, and

2. every A in NP is polynomial time reducible to B

### Polynomial Time Reducible

• Problem A reduces to problem B iff there is a function f such that

wAf(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!

• That is, use the solution of B to come up with a solution of A
• Polynomial time reducible means that f is a polynomial time function.

### Theorem 7.35: NP Completeness and P = NP

• Theorem 7.35: If B is NP-complete and B ∈ P, then P = NP.

• Proof follows directly from definition of polynomial time reducibility.

### Cook-Levin Theorem, Revisited

• 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!

• Proof idea: Convert every input w to A into a Boolean formula

### An Alternate, Equivalent Definition of NP

• 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

### Some Final Problems

• 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

• Example: (x ∨ y) ∧ (y ∨ z)
• CLIQUE and 3SAT are both NP-complete