CS310 : Automata Theory 2020

(1)

CS310 : Automata Theory 2020

Lecture 32: The complexity class NP and NP completeness

Instructor: S. Akshay

IITB, India

Spring 2020

(2)

CS310 : Automata Theory 2020 Instructor: S. Akshay IITB, India 2

Recap

Turing machines and computability 1. Turing machines

(i) Definition & variants

(ii) Decidable and Turing recognizable languages (iii) Church-Turing Hypothesis

2. Undecidability

(i) A proof technique by diagonalization (ii) Via reductions

(iii) Rice’s theorem

3. Applications: showing (un)decidability of other problems (i) A string matching problem: Post’s Correspondance Problem (ii) A problem for compilers: Unambiguity of Context-free languages 4. Efficiency in computation: run-time complexity.

(i) Running time complexity

(ii) Polynomial and exponential time complexity

(3)

Recap

2. Undecidability

(i) Running time complexity

(4)

Recap

2. Undecidability

3. Applications: showing (un)decidability of other problems (i) A string matching problem: Post’s Correspondance Problem (ii) A problem for compilers: Unambiguity of Context-free languages

4. Efficiency in computation: run-time complexity. (i) Running time complexity

(5)

Recap

2. Undecidability

(6)

This lecture

The complexity class NP

In this lecture we will cover I The NP complexity class I The P vs NP problem I NP completeness

I The Cook-Levin Theorem Reading Material

I Section 10.1, 10.2, 10.3 , Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullman

I Section 7.3, 7.4, Introduction to the Theory of Computation, Michael Sipser

(7)

This lecture

The complexity class NP

In this lecture we will cover I The NP complexity class I The P vs NP problem I NP completeness

I The Cook-Levin Theorem Reading Material

I Section 10.1, 10.2, 10.3, Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullman

(8)

The class NP

NTIME(t(n)) is set of all languages decidable by aO(t(n)) 1-tape non-det Turing machine

Definition

NP is the class of languages that are decidable in polynomial time on a non-deterministic single-tape Turing machine, i.e.,

NP =[

k

NTIME(n^k)

Verifier

for languageAis an algorithm V s.t. w ∈A iffV accepts hw,ci for some witness or proof stringc. Examples: HAMPATH, Composities

Theorem

A language is in NP iff it has a poly-time verifier

(9)

The class NP

Definition

NP =[

k

NTIME(n^k)

Verifier

for languageAis an algorithm V s.t. w ∈A iffV accepts hw,ci for some witness or proof stringc. Examples: HAMPATH, Composities

Theorem

(10)

The class NP

Definition

NP =[

k

NTIME(n^k)

Verifier

for language Ais an algorithm V s.t. w ∈A iffV accepts hw,ci for some witness or proof string c.

Examples: HAMPATH, Composities Theorem

(11)

The class NP

Definition

NP =[

k

NTIME(n^k)

Verifier

for language Ais an algorithm V s.t. w ∈A iffV accepts hw,ci for some witness or proof string c. Examples: HAMPATH, Composities

Theorem

(12)

The class NP

Definition

NP =[

k

NTIME(n^k)

Verifier

for language Ais an algorithm V s.t. w ∈A iffV accepts hw,ci for some witness or proof string c. Examples: HAMPATH, Composities

Theorem

(13)

Non-determinism vs Poly-time verifiers

Theorem

(14)

Non-determinism vs Poly-time verifiers

Theorem

A language is in NP iff it has a poly-time verifier I =⇒

(15)

Non-determinism vs Poly-time verifiers

Theorem

I =⇒ SupposeN is the NTM that decidesL∈NP, we define verifier V: I On input hw,ci, where w,c are strings,

(16)

Non-determinism vs Poly-time verifiers

Theorem

1. SimulateN onw, withc as a description of the non-det choice.

2. If this branch ofN’s computation accepts, accept, else reject.

(17)

Non-determinism vs Poly-time verifiers

Theorem

I ⇐= Given verifierV which runs in timen^k, we construct NTM N as follows:

I On input w of lengthn;

(18)

Non-determinism vs Poly-time verifiers

Theorem

I ⇐= Given verifierV which runs in timen^k, we construct NTM N as follows:

I On input w of lengthn;

1. Guess (i.e., non-det choice) stringc of length at mostn^k 2. RunV on hw,ci

3. Accept ifV accepts, else reject

(19)

Examples of problems in NP class

Exercises

I CLIQUE: Does an undir graph G contain a clique of sizek? I SUBSET-SUM: Given a set of numbers, does some set add up to

exactly S?

CLIQUE:{hG,ki |G is an undirected graph with ak-clique}. Give two proofs!

(20)

Examples of problems in NP class

Exercises

I CLIQUE: Does an undir graph G contain a clique of sizek? I SUBSET-SUM: Given a set of numbers, does some set add up to

exactly S?

CLIQUE: {hG,ki |G is an undirected graph with ak-clique}. Give two proofs!

(21)

The start of many many questions

What about complementation?

I Is CLIQUES in NP?

I We define Co-NP for problems whose complement is in NP. I Give an example of a problem in Co-NP. COMPOSITES I Is NP separated from Co-NP?

What aboutNP vs EXPTIME? I NP ⊆EXPTIME, but is it strict?

One question to rule them all: isP =NP?

Also ifP =NP, then what happens to the earlier questions?

(22)

The start of many many questions

I IsCLIQUES in NP?

I We define Co-NP for problems whose complement is in NP. I Give an example of a problem in Co-NP. COMPOSITES I Is NP separated from Co-NP?

(23)

The start of many many questions

I IsCLIQUES in NP?

I We define Co-NP for problems whose complement is in NP.

I Give an example of a problem in Co-NP. COMPOSITES I Is NP separated from Co-NP?

(24)

The start of many many questions

I IsCLIQUES in NP?

I Give an example of a problem in Co-NP.

COMPOSITES I Is NP separated from Co-NP?

(25)

The start of many many questions

I IsCLIQUES in NP?

I Give an example of a problem in Co-NP. COMPOSITES

I Is NP separated from Co-NP?

(26)

The start of many many questions

I IsCLIQUES in NP?

(27)

The start of many many questions

I IsCLIQUES in NP?

What about NP vs EXPTIME?

I NP ⊆EXPTIME, but is it strict?

(28)

The start of many many questions

I IsCLIQUES in NP?

What about NP vs EXPTIME? I NP ⊆EXPTIME, but is it strict?

(29)

The start of many many questions

I IsCLIQUES in NP?

One question to rule them all: is P =NP?

(30)

The start of many many questions

I IsCLIQUES in NP?

One question to rule them all: is P =NP?

Also if P =NP, then what happens to the earlier questions?

(31)

The P vs NP problem

I P: class of problems solvable in polynomial time I NP: class of problems verifiable in polynomial time

= class of problems solvable in polynomial time in a non-determistic TM. I EXP: class of problems solvable in exponential time.

I Co− C: class of problems whose complement is solvable inC.

(32)

The P vs NP problem

I P: class of problems solvable in polynomial time I NP: class of problems verifiable in polynomial time

= class of problems solvable in polynomial time in a non-determistic TM.

I EXP: class of problems solvable in exponential time.

I Co− C: class of problems whose complement is solvable in C.

(33)

NP completeness

The problem of satisfiability SAT

Given a Boolean formula, i.e., an expression with Boolean variables and operations, does it have a satisfying assignment?

SAT ={hφi |φis a satisfiable Boolean formula.} Example: φ= (x∧y∧z)∨(x∧z)

Theorem

SAT ∈P iff P =NP

SAT ={hφi |φ is a satisfiable 3-cnf-formula.} where 3-cnf-formula is a formula in special form:

I conjunction of “clauses”

I each clause has literals, i.e., variables or their negations, separated by disjunction

I each clause has 3 literals

(34)

NP completeness

SAT ={hφi |φis a satisfiable Boolean formula.}

Example: φ= (x∧y∧z)∨(x∧z) Theorem

SAT ∈P iff P =NP

(35)

NP completeness

Example: φ= (x∧y∧z)∨(x∧z)

Theorem

SAT ∈P iff P =NP

(36)

NP completeness

SAT ∈P iff P =NP

(37)

NP completeness

SAT ∈P iff P =NP

SAT ={hφi |φ is a satisfiable 3-cnf-formula.}

where 3-cnf-formula is a formula in special form:

I each clause has literals, i.e., variables or their negations, separated by

(38)

Polynomial time reductions

Ptime computable functions

f : Σ^∗ →Σ^∗ is Ptime computable if there is a polytime TMM, which started on any input w halts with justf(w) on its tape.

Polynomial time reduction

LanguageApolynomtial time reducible to B, denoted A≤_P B if there is a Ptime computable functionf s.t.

w ∈A⇔f(w)∈B Such a function is called a Ptime reduction ofA toB. Theorem

IfA≤_pB andB ∈P, then A∈P

(Note: if there is a “halting TM” reduction fromAto B, then Aundecidable impliedB undecidable!)

(39)

Polynomial time reductions

Language Apolynomtial time reducible to B, denoted A≤_P B if there is a Ptime computable function f s.t.

w ∈A⇔f(w)∈B Such a function is called a Ptime reduction of A toB.

Theorem

(40)

Polynomial time reductions

Theorem

(41)

Polynomial time reductions

Theorem

(42)

Exercise (H.W)

I Show that 3SAT is polytime reducible to CLIQUE.

I Show that 3SAT is polytime reducible to SUBSETSUM.

(43)

NP-completeness

Definition

A languageB is NP-complete if two conditions hold:

1. B is in NP,

2. every Ain NP is polynomial time reducible to B

If only condition 2 holdsB is said to be NP-hard. Exercises:

I IfB is NP-complete, and B∈P, thenP =NP. I IfB is NP-complete, and B≤_P C, thenC is NP-hard. The Cook-Levin Theorem

SAT is NP-complete.

Proof: Reading exercise! Section 7.5 from Sipser’s book or Section 10.2 from Hopcroft, Motwani, Ullman’s book.

(44)

NP-completeness

Definition

1. B is in NP,

2. every Ain NP is polynomial time reducible to B If only condition 2 holds B is said to be NP-hard.

Exercises:

I IfB is NP-complete, and B∈P, thenP =NP. I IfB is NP-complete, and B≤_P C, thenC is NP-hard. The Cook-Levin Theorem

SAT is NP-complete.

(45)

NP-completeness

Definition

1. B is in NP,

Exercises:

I IfB is NP-complete, and B∈P, thenP =NP.

I IfB is NP-complete, and B≤_P C, thenC is

NP-hard.

The Cook-Levin Theorem SAT is NP-complete.

(46)

NP-completeness

Definition

1. B is in NP,

Exercises:

I IfB is NP-complete, and B≤_P C, thenC is NP-hard.

(47)

NP-completeness

Definition

1. B is in NP,

Exercises:

(48)

NP-completeness

Definition

1. B is in NP,

Exercises:

(49)

Cook-Levin Theorem

I SAT ∈NP.

I Take any language A∈NP and show it is polytime reducible to SAT. I Reduction via computation histories!

Sketch: Step 1 - language to tableau 1. Spse N is NTM decides Ain n^k time.

2. Writen^k×n^k tableau for each computation ofN onw, rows are config. 3. Every accepting tableau (some config is acc) is an accepting

computation branch of N onw.

4. Thus, N acc w iff there exists an accepting tableau forN onw.

(50)

Cook-Levin Theorem

I SAT ∈NP.

I Take any language A∈NP and show it is polytime reducible to SAT. I Reduction via computation histories!

(51)

Cook-Levin Theorem

I SAT ∈NP.

I Take any language A∈NP and show it is polytime reducible to SAT.

I Reduction via computation histories! Sketch: Step 1 - language to tableau

1. Spse N is NTM decides Ain n^k time.

(52)

Cook-Levin Theorem

I SAT ∈NP.

I Reduction via computation histories!

(53)

Cook-Levin Theorem

I SAT ∈NP.

(54)

Cook-Levin Theorem

I SAT ∈NP.

2. Writen^k×n^k tableau for each computation ofN onw, rows are config.

3. Every accepting tableau (some config is acc) is an accepting computation branch of N onw.

(55)

Cook-Levin Theorem

I SAT ∈NP.

(56)

Cook-Levin Theorem

I SAT ∈NP.

(57)

Cook-Levin Theorem (Contd.)

Sketch: Step 2 - language to tableau to SAT Given N and w, produce formulaϕ:

1. Variable x_i,j,s for each 1≤i,j ≤n^k,s ∈C =Q∪Γ∪ {#}. 2. Idea: cell[i,j] =s iff xi,j,s = 1.

3. Design ϕs.t., SAT assignment corresponds to acc tableau forN on w. 4. ϕ=ϕ_cell ∧ϕ_start∧ϕ_move∧ϕ_acc

(58)

Cook-Levin Theorem (Contd.)

1. Variable x_i,j,s for each 1≤i,j ≤n^k,s ∈C =Q∪Γ∪ {#}.

2. Idea: cell[i,j] =s iff xi,j,s = 1.

(59)

Cook-Levin Theorem (Contd.)

(60)

Cook-Levin Theorem (Contd.)

3. Design ϕs.t., SAT assignment corresponds to acc tableau forN on w.

4. ϕ=ϕ_cell ∧ϕ_start∧ϕ_move∧ϕ_acc

(61)

Cook-Levin Theorem (Contd.)

(62)

Cook-Levin Theorem (Contd.)

Sketch: Step 3 - SAT formula

ϕ=ϕ_cell ∧ϕstart∧ϕmove ∧ϕacc where,

1. for each cell one variable is “on”, and only one is: ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j,s∧W

s6=t∈C(x_i,j_,s ∨x_i,j_,t)] 2. start encodes that first row is starting config:

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

3. accept says that accepting config should occur somewhere in tableau ϕ_acc =W

1≤i,j≤n^kx_i,j,q_acc

4. move encodes that each row correponds to config that “legally” follows the preceding row config acc to N

ϕmove =V

1,≤i,j<n^k (the (i,j)-window is legal)

(63)

Cook-Levin Theorem (Contd.)

1. for each cell one variable is “on”, and only one is:

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j,s∧W

s6=t∈C(x_i,j_,s ∨x_i,j_,t)] 2. start encodes that first row is starting config:

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(64)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

s6=t∈C(x_i,j_,s∨x_i,j_,t)]

2. start encodes that first row is starting config: ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(65)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

2. start encodes that first row is starting config:

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(66)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(67)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

3. accept says that accepting config should occur somewhere in tableau

ϕ_acc =W

ϕmove =V

(68)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

1≤i,j≤n^kx_i,j_,q_acc

ϕmove =V

(69)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(70)

Cook-Levin Theorem (Contd.)

ϕ_cell =V

1≤i,j≤n^k[W

s∈Cx_i,j_,s ∧W

ϕ_start =x_1,1,#∧x_1,2,q₀∧. . .

ϕmove =V

(71)

Cook-Levin Theorem (Contd.)

Step 3 (Contd.) - Encoding NTM as SAT

ϕ_move encodes that each row corresponds to config that “legally” follows preceding row acc to N

(72)

Cook-Levin Theorem (Contd.)

ϕmove encodes that each row corresponds to config that “legally” follows preceding row acc to N

1. enough to ensure that each 2×3 window of cells is legal, i.e., does not violate the transition function of N.

(73)

Cook-Levin Theorem (Contd.)

2. legal windows are “like” the dominos that we used in PCP!

(74)

Cook-Levin Theorem (Contd.)

ϕmove encodes that each row corresponds to config that “legally” follows preceding row acc to N

3. Ex: Give 3 examples of legal windows and 3 illegal windows, given δ(q,a) ={q,b,R},δ(q,b) ={(q⁰,c,L),(q⁰,a,R)}

(75)

Cook-Levin Theorem (Contd.)

3. Claim: If top row is start, every window is legal, then each row is config that follows prev one.

(76)

Cook-Levin Theorem (Contd.)

ϕmove = ^

1≤i,j<n^k

((i,j)−window is legal)

(77)

Cook-Levin Theorem (Contd.)

ϕ_move = ^

1≤i,j<n^k

((i,j)−window is legal)

Encode this as a disjunct W

a...a is legal(x_i,j−1,a1)∧x_i,j,a₂∧...)

(78)

Cook-Levin Theorem (Completed!)

Completing the proof

I N has an acc computation onw iff ϕis SAT.

For detailed proof, read: Section 7.5 from Sipser’s book or Section 10.2 from Hopcroft, Motwani, Ullman’s book.

(79)

Cook-Levin Theorem (Completed!)

I Size of formula isO(n^2k) and can be constructed in polynomial time (from w).

(80)

Cook-Levin Theorem (Completed!)

1. No. of cells is (n^k)²=n^2k, no. of cells in top row isn^k.

(81)

Cook-Levin Theorem (Completed!)

1. No. of cells is (n^k)²=n^2k, no. of cells in top row isn^k. 2. ϕ_start is O(n^k) (why?)

(82)

Cook-Levin Theorem (Completed!)

1. No. of cells is (n^k)²=n^2k, no. of cells in top row isn^k. 2. ϕstart is O(n^k) (why?)

3. All others are fixed size for each cell =O(n^2k)

(83)

Cook-Levin Theorem (Completed!)

1. No. of cells is (n^k)²=n^2k, no. of cells in top row isn^k. 2. ϕ_start is O(n^k) (why?)

4. Can be constructed in polynomial time fromN,w, i.e., polytime reduction For detailed proof, read: Section 7.5 from Sipser’s book or Section 10.2 from Hopcroft, Motwani, Ullman’s book.

(84)

Cook-Levin Theorem (Completed!)

1. No. of cells is (n^k)²=n^2k, no. of cells in top row isn^k. 2. ϕstart is O(n^k) (why?)

4. Can be constructed in polynomial time fromN,w, i.e., polytime reduction Thus, we have a PTime reduction from any NP problem to SAT, i.e., SAT is NP-hard.

(85)

NP-completeness examples

1. 3SAT is NP-complete. (why?)

2. CLIQUE is NP-complete. 3. SUBSETSUM is NP-complete. 4. Vertex cover is NP-complete.

5. A whole growing book of NP-complete problems! (Garey-Johnson) So, why are so many natural problems either inP or NP-complete? Well, there are some natural problems that are not known to be inP, but that are inNP and not known to beNP-hard.

(86)

NP-completeness examples

1. 3SAT is NP-complete. (why?) 2. CLIQUE is NP-complete.

3. SUBSETSUM is NP-complete. 4. Vertex cover is NP-complete.

(87)

NP-completeness examples

3. SUBSETSUM is NP-complete.

4. Vertex cover is NP-complete.

(88)

NP-completeness examples

(89)

NP-completeness examples

5. A whole growing book of NP-complete problems! (Garey-Johnson)

So, why are so many natural problems either inP or NP-complete? Well, there are some natural problems that are not known to be inP, but that are inNP and not known to beNP-hard.

(90)

NP-completeness examples

5. A whole growing book of NP-complete problems! (Garey-Johnson) So, why are so many natural problems either in P or NP-complete?

Well, there are some natural problems that are not known to be inP, but that are inNP and not known to beNP-hard.

(91)

NP-completeness examples

5. A whole growing book of NP-complete problems! (Garey-Johnson) So, why are so many natural problems either in P or NP-complete?

Well, there are some natural problems that are not known to be in P, but that are in NP and not known to be NP-hard.

(92)

Getting around NP-hardness

Many problems are NP-complete. So what do people do?

An algorithmician’s answer:

1. Approximate!

2. Randomize. 3. Parametrize. 4. Quantize!

5. average/amortized/smoothed complexity.

A practitioner’s answer

1. What hardness? SAT is easy (almost always)!

2. The advent of SAT-solvers. Can solve SAT queries on millions of variables in seconds!

3. Goal nowadays: develop efficient encodinginto SAT!

(93)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize. 4. Quantize!

(94)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

(95)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

(96)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

(97)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

(98)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

(99)

Getting around NP-hardness

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!

2. The advent of SAT-solvers. Can solve SAT queries on millions of