# CS代考计算机代写 AI algorithm BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation

Lecture 21:

• NP-Completeness

• Cook-Levin Theorem • Reductions

Mark Bun April 15, 2020

Reading:

Sipser Ch 7.3-7.5

Last time: Two equivalent definitions of NP 1) NP is the class of languages decidable in polynomial time

on a nondeterministic TM

NP = ⋃∞ NTIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1

2) A polynomial-time verifier for a language 𝐿𝐿 is a deterministic poly( 𝑤𝑤 )-time algorithm 𝑉𝑉 such that 𝑤𝑤 ∈ 𝐿𝐿 iff there exists a string 𝑐𝑐 such that 𝑉𝑉( 𝑤𝑤, 𝑐𝑐 ) accepts

Theorem: A language 𝐿𝐿 ∈ NP iff there is a polynomial-time verifier for 𝐿𝐿

4/15/2020 CS332 – Theory of Computation 2

Examples of NP languages: SAT

“Is there an assignment to the variables in a logical

formula that make it evaluate to true?”

• Boolean variable: Variable that can take on the value

true/false (encoded as 0/1)

• Boolean operations: ∧ AND , ∨ OR , ¬ (NOT)

• Boolean formula: Expression made of Boolean variables and operations. Ex: (𝑥𝑥 ∨ 𝑥𝑥 ) ∧ 𝑥𝑥

123

• An assignment of 0s and 1s to the variables satisfies a formula 𝜑𝜑 if it makes the formula evaluate to 1

• A formula 𝜑𝜑 is satisfiable if there exists an assignment that satisfies it

4/15/2020 CS332 – Theory of Computation 3

Examples of NP languages: SAT

Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥3 Satisfiable?

Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥2 Satisfiable? 𝑆𝑆𝑆𝑆𝑆𝑆 = { 𝜑𝜑 |𝜑𝜑 is a satisfiable formula}

Claim: 𝑆𝑆𝑆𝑆𝑆𝑆 ∈ NP

4/15/2020 CS332 – Theory of Computation 4

Examples of NP languages: TSP

“Given a list of cities and distances between them, is

there a ‘short’ tour of all of the cities?”

• A number of cities 𝑚𝑚

More precisely: Given

• A function 𝐷𝐷: {1, … , 𝑚𝑚} 2 → N giving the distance between each pair of cities

• A distance bound 𝐵𝐵

𝑆𝑆𝑆𝑆𝑇𝑇 = { 𝑚𝑚, 𝐷𝐷, 𝐵𝐵 |∃ a tour visiting every city

with length ≤ 𝐵𝐵}

4/15/2020 CS332 – Theory of Computation 5

P vs. NP

Question: Does P = NP?

Philosophically: Can every problem with an efficiently verifiable solution also be solved efficiently?

A central problem in mathematics and computer science

EXP

NP

EXP

P

P = NP

If P=NP

If P≠NP 4/15/2020

CS332 – Theory of Computation 6

A world where P = NP

• Many important decision problems can be solved in

polynomial time (𝐻𝐻𝑆𝑆𝐻𝐻𝑇𝑇𝑆𝑆𝑆𝑆𝐻𝐻, 𝑆𝑆𝑆𝑆𝑆𝑆, 𝑆𝑆𝑆𝑆𝑇𝑇, etc.)

• Many search problems can be solved in polynomial time

(e.g., given a natural number, find a prime factorization)

• Many optimization problems can be solved in polynomial time (e.g., find the lowest energy conformation of a protein)

4/15/2020 CS332 – Theory of Computation 7

A world where P = NP

• Secure cryptography becomes impossible

An NP search problem: Given a ciphertext 𝐶𝐶, find a plaintext 𝑚𝑚 and encryption key 𝑘𝑘 that would encrypt to 𝐶𝐶

• AI / machine learning become easy: Identifying a consistent classification rule is an NP search problem

• Finding mathematical proofs becomes easy: NP search problem: Given a mathematical statement 𝑆𝑆 and length bound 𝑘𝑘, is there a proof of 𝑆𝑆 with length at most 𝑘𝑘?

General consensus: P ≠ NP

4/15/2020 CS332 – Theory of Computation 8

NP-Completeness

4/15/2020 CS332 – Theory of Computation 9

What about a world where P ≠ NP Believe this to be true, but very far from proving it

P ≠ NP implies that there is a problem in NP which cannot be solved in polynomial time, but it might not be a useful one

Question: What would P ≠ NP allow us to conclude about problems we care about?

Idea: Identify the “hardest” problems in NP Find𝐿𝐿∈NPsuchthat𝐿𝐿∈P iff P=NP

4/15/2020 CS332 – Theory of Computation 10

Recall: Mapping reducibility

A function 𝑓𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝐻𝐻 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.

Definition:

Definition:

Language 𝑆𝑆 is mapping reducible to language 𝐵𝐵, written

𝑆𝑆 ≤m 𝐵𝐵

if there is a computable function 𝑓𝑓: Σ∗ → Σ∗ such that for

all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝑆𝑆 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵

4/15/2020 CS332 – Theory of Computation 11

Polynomial-time reducibility

A function 𝑓𝑓: Σ∗ → Σ∗ is polynomial-time computable if there is a polynomial-time TM 𝐻𝐻 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.

Definition:

Language 𝑆𝑆 is polynomial-time reducible to language 𝐵𝐵,

Definition:

𝑆𝑆 ≤p 𝐵𝐵

written

if there is a polynomial-time computable function 𝑓𝑓: Σ∗ → Σ∗

such that for all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝑆𝑆 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵 4/15/2020 CS332 – Theory of Computation 12

Implications of poly-time reducibility

Theorem:If𝑆𝑆≤p 𝐵𝐵and𝐵𝐵∈𝑇𝑇,then𝑆𝑆∈𝑇𝑇

Proof: Let 𝐻𝐻 decide 𝐵𝐵 in poly time, and let 𝑓𝑓 be a poly- time reduction from 𝑆𝑆 to 𝐵𝐵. The following TM decides 𝑆𝑆 in poly time:

4/15/2020 CS332 – Theory of Computation 13

NP-completeness

Definition: A language 𝐵𝐵 is NP-complete if 1) 𝐵𝐵 ∈ NP, and

2) Every language 𝑆𝑆 ∈ NP is poly-time reducible to 𝐵𝐵, i.e., 𝑆𝑆 ≤p 𝐵𝐵 (“𝐵𝐵 is NP-hard”)

4/15/2020 CS332 – Theory of Computation 14

Implications of NP-completeness

Theorem: Suppose 𝐵𝐵 is NP-complete.

Then 𝐵𝐵 ∈ P iff P = NP Proof:

4/15/2020 CS332 – Theory of Computation 15

Implications of NP-completeness

Theorem: Suppose 𝐵𝐵 is NP-complete.

Then 𝐵𝐵 ∈ P iff P = NP Consequences of 𝐵𝐵 being NP-complete:

1) If you want to show P = NP, you just have to show 𝐵𝐵∈P

2) If you want to show P ≠ NP, you just have to show 𝐵𝐵∉P

3) If you already believe P ≠ NP, then you believe 𝐵𝐵 ∉ P 4/15/2020 CS332 – Theory of Computation 16

Cook-Levin Theorem and NP-Complete Problems

4/15/2020 CS332 – Theory of Computation 17

Cook-Levin Theorem

Theorem: 𝑆𝑆𝑆𝑆𝑆𝑆 (Boolean satisfiability) is NP-complete Proof: Already know 𝑆𝑆𝑆𝑆𝑆𝑆 ∈ P. Need to show every

problem in NP reduces to 𝑆𝑆𝑆𝑆𝑆𝑆 (later?)

Stephen A. Cook (1971)

Leonid Levin (1973)

4/15/2020 CS332 – Theory of Computation

18

New NP-complete problems from old

Lemma:If𝑆𝑆≤p 𝐵𝐵and𝐵𝐵≤p 𝐶𝐶,then𝑆𝑆≤p 𝐶𝐶 (poly-time reducibility is transitive)

Theorem: If 𝐶𝐶 ∈ NP and 𝐵𝐵 ≤p 𝐶𝐶 for some NP-complete language 𝐵𝐵, then 𝐶𝐶 is also NP-complete

4/15/2020 CS332 – Theory of Computation 19

New NP-complete problems from old

All problems below are NP-complete and hence poly-time reduce to one another!

by definition of NP-completeness

SAT

3SAT

DIR-HAM-CYCLE

GRAPH 3-COLOR

SUBSET-SUM

HAM-CYCLE

PLANAR 3-COLOR

SCHEDULING

TSP

INDEPENDENT SET

VERTEX COVER

SET COVER

4/15/2020 CS332 – Theory of Computation

20

3𝑆𝑆𝑆𝑆𝑆𝑆 (3-CNF Satisfiability) Definition(s):

• A literal either a variable of its negation 𝑥𝑥 , 𝑥𝑥 57

• A clause is a disjunction (OR) of literals Ex. 𝑥𝑥5 ∨ 𝑥𝑥7 ∨ 𝑥𝑥2 • A 3-CNF is a conjunction (AND) of clauses where each

clause contains exactly 3 literals Ex.𝐶𝐶 ∧𝐶𝐶 ∧…∧𝐶𝐶 =

12𝑚𝑚

𝑥𝑥5∨𝑥𝑥7∨𝑥𝑥2 ∧ 𝑥𝑥3∨𝑥𝑥4∨𝑥𝑥1 ∧⋯∧ 𝑥𝑥1∨𝑥𝑥1∨𝑥𝑥1

3𝑆𝑆𝑆𝑆𝑆𝑆 = 𝜑𝜑 𝜑𝜑isasatisfiable3−CNF

4/15/2020 CS332 – Theory of Computation 21

3𝑆𝑆𝑆𝑆𝑆𝑆 is NP-complete Theorem: 3𝑆𝑆𝑆𝑆𝑆𝑆 is NP-complete Proof idea: 1) 3𝑆𝑆𝑆𝑆𝑆𝑆 is in NP (why?)

2) Show that 𝑆𝑆𝑆𝑆𝑆𝑆 ≤p 3𝑆𝑆𝑆𝑆𝑆𝑆

Idea of reduction: Given a poly-time algorithm converting an arbitrary formula 𝜑𝜑 into a 3CNF 𝜓𝜓 such that 𝜑𝜑 is satisfiable iff 𝜓𝜓 is satisfiable

4/15/2020 CS332 – Theory of Computation 22

Some general reduction strategies

Ex. 𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆 ≤

and 𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 ≤p 𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆

• Reduction by simple equivalence

Ex. 𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 ≤ • Gadget reductions

𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉

p

𝑆𝑆𝐼𝐼𝑆𝑆 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆

CS332 – Theory of Computation 23

• Reduction from special case to general case

Ex. 3𝑆𝑆𝑆𝑆𝑆𝑆 ≤ 4/15/2020

p p

Independent Set

An independent set in an undirected graph 𝐺𝐺 is a set of vertices that includes at most one endpoint of every edge.

𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆

= 𝐺𝐺, 𝑘𝑘 𝐺𝐺 is an undirected graph containing an independent set with ≥ 𝑘𝑘 vertices}

• Is there an independent set of size ≥ 6?

• Yes.

• Is there an independent set of size ≥ 7?

• No.

independent set

4/15/2020 CS332 – Theory of Computation 24

Independent Set is NP-complete

1) 𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆 ∈ NP

2) Reduce 3𝑆𝑆𝑆𝑆𝑆𝑆 ≤p 𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝑇𝑇𝐼𝐼𝐼𝐼𝐷𝐷𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆

Proof. “On input 𝜑𝜑 , where 𝜑𝜑 is a 3CNF formula, 1. Construct graph 𝐺𝐺 from 𝜑𝜑

2.

Output 𝐺𝐺, 𝑘𝑘 , where 𝑘𝑘 is the number of clauses in 𝜑𝜑.”

4/15/2020 CS332 – Theory of Computation 25

• 𝐺𝐺 contains 3 vertices for each clause, one for each literal. • Connect 3 literals in a clause in a triangle.

• Connect literal to each of its negations.

Example of the reduction

𝜑𝜑= 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥3 ∧ 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥3 ∧ 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥3

4/15/2020 CS332 – Theory of Computation 26

Proof of correctness for reduction

Let 𝑘𝑘 = # clauses and 𝑙𝑙 = # literals in 𝜑𝜑

Claim: 𝜑𝜑 is satisfiable iff 𝐺𝐺 has an ind. set of size 𝑘𝑘

⟹ Given a satisfying assignment, select one literal from each triangle. This is an ind. set of size 𝑘𝑘

⟸ Let 𝑆𝑆 be an ind. set of size 𝑘𝑘

• 𝑆𝑆 must contain exactly one vertex in each triangle

• Set these literals to true, and set all other variables in an arbitrary way

• Truth assignment is consistent and all clauses satisfied

Runtime: 𝑂𝑂(𝑘𝑘 + 𝑙𝑙2) which is polynomial in input size

4/15/2020 CS332 – Theory of Computation 27