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

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

A = {

w|Vaccepts <w, c> for some stringc}

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*

- Certificate is

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

- 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 itNo 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 = NPLet 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, andevery

*A*in NP is polynomial time reducible to*B*

- 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*

- That is, use the solution of
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-completeProof of 1: Easy to show

*SAT*∈ NPProof 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

- Proof idea: Convert every input

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- Example: (
*x ∨ y) ∧ (y ∨ z)*

- Example: (

*CLIQUE*and*3SAT*are both NP-complete