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