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:

  • φ = x ∧ y is satisfiable

  • φ = x ∧ x' is not satisfiable

  • φ = (x' ∧ y) ∨ (x ∧ z') 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

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!

  • 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