PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 23:
• NP-completeness
Reading:
Sipser Ch 7.4-7.5
Mark Bun
April 21, 2021
Last time: Two equivalent definitions of NP
1) NP is the class of languages decidable in polynomial time
on a nondeterministic TM
NP = ⋃𝑘𝑘=1
∞ NTIME(𝑛𝑛𝑘𝑘)
2) A polynomial-time verifier for a language 𝐿𝐿 is a
deterministic poly( 𝑤𝑤 )-time algorithm 𝑉𝑉 such that 𝑤𝑤 ∈ 𝐿𝐿
iff there exists a certificate 𝑐𝑐 such that 𝑉𝑉( 𝑤𝑤, 𝑐𝑐 ) accepts
Theorem: A language 𝐿𝐿 ∈ NP iff there is a polynomial-time
verifier for 𝐿𝐿
4/21/2021 CS332 – Theory of Computation 2
NP-Completeness
4/21/2021 CS332 – Theory of Computation 3
Understanding the P vs. NP question
Believe P ≠ NP, but very far from proving it
Question 1: How can studying specific computational
problems help us get a handle on resolving P vs. NP?
Question 2: What would P ≠ NP allow us to conclude
about specific problems we care about?
Idea: Identify the “hardest” problems in NP
Find 𝐿𝐿 ∈ NP such that 𝐿𝐿 ∈ P iff P = NP
4/21/2021 CS332 – Theory of Computation 4
Recall: Mapping reducibility
Definition:
A function 𝑓𝑓:Σ∗ → Σ∗ is computable if there is a TM 𝑀𝑀
which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on
its tape.
Definition:
Language 𝐴𝐴 is mapping reducible to language 𝐵𝐵, written
𝐴𝐴 ≤m 𝐵𝐵
if there is a computable function 𝑓𝑓:Σ∗ → Σ∗ such that for
all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵
4/21/2021 CS332 – Theory of Computation 5
Polynomial-time reducibility
Definition:
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 𝐵𝐵,
written
𝐴𝐴 ≤p 𝐵𝐵
if there is a polynomial-time computable function 𝑓𝑓:Σ∗ → Σ∗
such that for all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵
4/21/2021 CS332 – Theory of Computation 6
Implications of poly-time reducibility
Theorem: If 𝐴𝐴 ≤p 𝐵𝐵 and 𝐵𝐵 ∈ P, then 𝐴𝐴 ∈ P
Proof: Let 𝑀𝑀 decide 𝐵𝐵 in poly time, and let 𝑓𝑓 be a poly-
time reduction from 𝐴𝐴 to 𝐵𝐵. The following TM decides 𝐴𝐴
in poly time:
4/21/2021 CS332 – Theory of Computation 7
Is NP closed under poly-time reductions?
If 𝐴𝐴 ≤p 𝐵𝐵 and 𝐵𝐵 is in NP, does that mean 𝐴𝐴 is also in NP?
a) Yes, the same proof works using NTMs instead of TMs
b) No, because the new machine is an NTM instead of a
deterministic TM
c) No, because the new NTM may not run in polynomial
time
d) No, because the new NTM may accept some inputs it
should reject
e) No, because the new NTM may reject some inputs it
should accept
4/21/2021 CS332 – Theory of Computation 8
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/21/2021 CS332 – Theory of Computation 9
Implications of NP-completeness
Theorem: Suppose 𝐵𝐵 is NP-complete.
Then 𝐵𝐵 ∈ P iff P = NP
Proof:
4/21/2021 CS332 – Theory of Computation 10
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/21/2021 CS332 – Theory of Computation 11
Cook-Levin Theorem and
NP-Complete Problems
4/21/2021 CS332 – Theory of Computation 12
Do NP-complete problems exist?
Theorem: 𝑇𝑇𝑀𝑀𝑇𝑇𝐴𝐴𝑇𝑇 = { 𝑁𝑁,𝑤𝑤, 1𝑡𝑡 ∣
NTM 𝑁𝑁 accepts input 𝑤𝑤 within 𝑡𝑡 steps} is NP-complete
Proof sketch: 1) 𝑇𝑇𝑀𝑀𝑇𝑇𝐴𝐴𝑇𝑇 ∈ NP: Certificate = 𝑡𝑡
nondeterministic guesses made by 𝑁𝑁, verifier checks that
𝑁𝑁 accepts 𝑤𝑤 within 𝑡𝑡 steps under those guesses.
2) 𝑇𝑇𝑀𝑀𝑇𝑇𝐴𝐴𝑇𝑇 is NP-hard: Let 𝐿𝐿 ∈ NP be decided by NTM
𝑁𝑁 running in time 𝑇𝑇(𝑛𝑛). The following poly-time TM
shows 𝐿𝐿 ≤p 𝑇𝑇𝑀𝑀𝑇𝑇𝐴𝐴𝑇𝑇:
“On input 𝑤𝑤 (an instance of 𝐿𝐿):
Output 〈𝑁𝑁,𝑤𝑤, 1𝑇𝑇 |𝑤𝑤| 〉.”
4/21/2021 CS332 – Theory of Computation 13
Cook-Levin Theorem
Theorem: 𝑇𝑇𝐴𝐴𝑇𝑇 (Boolean satisfiability) is NP-complete
“Proof”: Already know 𝑇𝑇𝐴𝐴𝑇𝑇 ∈ NP. (Much) harder direction:
Need to show every problem in NP reduces to 𝑇𝑇𝐴𝐴𝑇𝑇
4/21/2021 CS332 – Theory of Computation 14
Stephen A. Cook (1971) Leonid Levin (1973)
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/21/2021 CS332 – Theory of Computation 15
New NP-complete problems from old
4/21/2021 CS332 – Theory of Computation 16
All problems below are NP-complete and hence poly-time reduce to one another!
SAT
3SAT
DIR-HAM-CYCLEINDEPENDENT SET
VERTEX COVER
GRAPH 3-COLOR
HAM-CYCLE
TSP
SUBSET-SUM
SCHEDULINGPLANAR 3-COLOR
SET COVER
by definition of NP-completeness
3𝑇𝑇𝐴𝐴𝑇𝑇 (3-CNF Satisfiability)
Definitions:
• A literal either a variable of its negation 𝑥𝑥5 , 𝑥𝑥7
• 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. 𝐶𝐶1 ∧ 𝐶𝐶2 ∧ … ∧ 𝐶𝐶𝑚𝑚 =
𝑥𝑥5 ∨ 𝑥𝑥7 ∨ 𝑥𝑥2 ∧ 𝑥𝑥3 ∨ 𝑥𝑥4 ∨ 𝑥𝑥1 ∧ ⋯∧ 𝑥𝑥1 ∨ 𝑥𝑥1 ∨ 𝑥𝑥1
3𝑇𝑇𝐴𝐴𝑇𝑇 = 𝜑𝜑 𝜑𝜑 is a satisfiable 3 − CNF
4/21/2021 CS332 – Theory of Computation 17
3𝑇𝑇𝐴𝐴𝑇𝑇 is NP-complete
Theorem: 3𝑇𝑇𝐴𝐴𝑇𝑇 is NP-complete
Proof idea: 1) 3𝑇𝑇𝐴𝐴𝑇𝑇 is in NP (why?)
2) Show that 𝑇𝑇𝐴𝐴𝑇𝑇 ≤p 3𝑇𝑇𝐴𝐴𝑇𝑇
Your classmate suggests the following reduction from 𝑇𝑇𝐴𝐴𝑇𝑇 to
3𝑇𝑇𝐴𝐴𝑇𝑇: “On input 𝜑𝜑, a 3-CNF formula (an instance of 3𝑇𝑇𝐴𝐴𝑇𝑇),
output 𝜑𝜑, which is already an instance of 𝑇𝑇𝐴𝐴𝑇𝑇.” Is this
reduction correct?
a) Yes, this is a poly-time reduction from 𝑇𝑇𝐴𝐴𝑇𝑇 to 3𝑇𝑇𝐴𝐴𝑇𝑇
b) No, because 𝜑𝜑 is not an instance of the 𝑇𝑇𝐴𝐴𝑇𝑇 problem
c) No, the reduction does not run in poly time
d) No, this is a reduction from 3𝑇𝑇𝐴𝐴𝑇𝑇 to 𝑇𝑇𝐴𝐴𝑇𝑇; it goes in the
wrong direction
4/21/2021 CS332 – Theory of Computation 18
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: Give a poly-time algorithm converting
an arbitrary formula 𝜑𝜑 into a 3CNF 𝜓𝜓 such that 𝜑𝜑 is
satisfiable iff 𝜓𝜓 is satisfiable
4/21/2021 CS332 – Theory of Computation 19
4/21/2021 CS332 – Theory of Computation 20
Converting 𝜑𝜑 to 𝜓𝜓
Independent Set
4/21/2021 CS332 – Theory of Computation 21
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
Independent Set is NP-complete
1) 𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝑁𝑁𝑇𝑇 − 𝑇𝑇𝐼𝐼𝑇𝑇 ∈ NP
2) Reduce 3𝑇𝑇𝐴𝐴𝑇𝑇 ≤p 𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝑁𝑁𝑇𝑇 − 𝑇𝑇𝐼𝐼𝑇𝑇
Proof of 1) The following gives a poly-time verifier for
𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝑁𝑁𝑇𝑇 − 𝑇𝑇𝐼𝐼𝑇𝑇
Certificate: Vertices 𝑣𝑣1, … , 𝑣𝑣𝑘𝑘
Verifier:
“On input 𝐺𝐺,𝑘𝑘; 𝑣𝑣1, … , 𝑣𝑣𝑘𝑘 , where 𝐺𝐺 is a graph, 𝑘𝑘 is a natural number,
1. Check that 𝑣𝑣1, … 𝑣𝑣𝑘𝑘 are distinct vertices in 𝐺𝐺
2. Check that there are no edges between the 𝑣𝑣𝑖𝑖’s.”
4/21/2021 CS332 – Theory of Computation 22
Independent Set is NP-complete
1) 𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝑁𝑁𝑇𝑇 − 𝑇𝑇𝐼𝐼𝑇𝑇 ∈ NP
2) Reduce 3𝑇𝑇𝐴𝐴𝑇𝑇 ≤p 𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑁𝑁𝐼𝐼𝐼𝐼𝑁𝑁𝑇𝑇 − 𝑇𝑇𝐼𝐼𝑇𝑇
Proof of 2) The following TM computes a poly-time reduction.
“On input 𝜑𝜑 , where 𝜑𝜑 is a 3CNF formula,
1. Construct graph 𝐺𝐺 from 𝜑𝜑
• 𝐺𝐺 contains 3 vertices for each clause, one for each literal.
• Connect 3 literals in a clause in a triangle.
• Connect every literal to each of its negations.
2. Output 𝐺𝐺,𝑘𝑘 , where 𝑘𝑘 is the number of clauses in 𝜑𝜑.”
4/21/2021 CS332 – Theory of Computation 23
Example of the reduction
4/21/2021 CS332 – Theory of Computation 24
𝜑𝜑 = 𝑥𝑥1 ∨ 𝑥𝑥2 ∨ 𝑥𝑥3 ∧ 𝑥𝑥1 ∨ 𝑥𝑥2 ∨ 𝑥𝑥3 ∧ 𝑥𝑥1 ∨ 𝑥𝑥2 ∨ 𝑥𝑥3
Proof of correctness for reduction
Let 𝑘𝑘 = # clauses and 𝑙𝑙 = # literals in 𝜑𝜑
Correctness: 𝜑𝜑 is satisfiable iff 𝐺𝐺 has an independent set of size 𝑘𝑘
⟹ Given a satisfying assignment, select one true literal from each
triangle. This is an independent set of size 𝑘𝑘
⟸ Let 𝑇𝑇 be an independent set in 𝐺𝐺 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 are satisfied
Runtime: 𝑂𝑂(𝑘𝑘 + 𝑙𝑙2) which is polynomial in input size
4/21/2021 CS332 – Theory of Computation 25
BU CS 332 – Theory of Computation
Last time: Two equivalent definitions of NP
NP-Completeness
Understanding the P vs. NP question
Recall: Mapping reducibility
Polynomial-time reducibility
Implications of poly-time reducibility
Is NP closed under poly-time reductions?
NP-completeness
Implications of NP-completeness
Implications of NP-completeness
Cook-Levin Theorem and NP-Complete Problems
Do NP-complete problems exist?
Cook-Levin Theorem
New NP-complete problems from old
New NP-complete problems from old
3𝑆𝐴𝑇 (3-CNF Satisfiability)
3𝑆𝐴𝑇 is NP-complete
3𝑆𝐴𝑇 is NP-complete
Converting 𝜑 to 𝜓
Independent Set
Independent Set is NP-complete
Independent Set is NP-complete
Example of the reduction
Proof of correctness for reduction