Lecture 41: Efficiency in computation Classifying problems by their complexity

(1)

CS310 : Automata Theory 2019

Lecture 41: Efficiency in computation Classifying problems by their complexity

Instructor: S. Akshay

IITB, India

16-04-2019

(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 (iii) Between TM and PDA: Linear Bounded Automata

4. Efficiency in computation: run-time complexity.

(i) Running time complexity: polynomial and exponential time (ii) Nondeterministic polynomial time, and thePvsNP problem. (iii) NP-completeness, the Cook-Levin Theorem.

(3)

Recap

2. Undecidability

(4)

Recap

2. Undecidability

(5)

Recap

2. Undecidability

(i) Running time complexity: polynomial and exponential time

(6)

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.

(7)

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.

(8)

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.

(9)

NP-completeness

Definition

1. B is in NP,

Exercises:

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

The Cook-Levin Theorem SAT is NP-complete.

(10)

NP-completeness

Definition

1. B is in NP,

Exercises:

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

(11)

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.

(12)

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!

(13)

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

(14)

Cook-Levin Theorem

I SAT ∈NP.

I Reduction via computation histories!

(15)

Cook-Levin Theorem

I SAT ∈NP.

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

(16)

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.

(17)

Cook-Levin Theorem

I SAT ∈NP.

(18)

Cook-Levin Theorem

I SAT ∈NP.

(19)

Cook-Levin Theorem (Contd.)

Sketch: Step 2 - language to tableau to SAT GivenN 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

(20)

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.

(21)

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.

(22)

Cook-Levin Theorem (Contd.)

(23)

Cook-Levin Theorem (Contd.)

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

(24)

Cook-Levin Theorem (Contd.)

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

(25)

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)

(26)

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

(27)

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

(28)

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

(29)

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

(30)

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

(31)

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

(32)

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

(33)

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

(34)

Cook-Levin Theorem (Contd.)

Step 3 - Encoding NTM as SAT

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

(35)

Cook-Levin Theorem (Contd.)

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

(36)

Cook-Levin Theorem (Contd.)

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

(37)

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)}

(38)

Cook-Levin Theorem (Contd.)

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

(39)

Cook-Levin Theorem (Contd.)

ϕ_move = ^

1≤i,j<n^k

((i,j)−window is legal)

(40)

Cook-Levin Theorem (Contd.)

ϕmove = ^

1≤i,j<n^k

((i,j)−window is legal)

Encode this as a disjunct W

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

(41)

Cook-Levin Theorem (Completed!)

Completing the proof

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

(42)

Cook-Levin Theorem (Completed!)

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

(43)

Cook-Levin Theorem (Completed!)

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

(44)

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?)

(45)

Cook-Levin Theorem (Completed!)

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

(46)

Cook-Levin Theorem (Completed!)

4. Can be constructed in polynomial time fromN,w, i.e., polytime reduction

(47)

Cook-Levin Theorem (Completed!)

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.

(48)

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.

(49)

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.

(50)

NP-completeness examples

3. SUBSETSUM is NP-complete.

4. Vertex cover is NP-complete.

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!

(56)

1. Approximate!

2. Randomize.

3. Parametrize.

4. Quantize!