Microsoft PowerPoint – CS332-Lec23-ann
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
1) is the class of languages decidable in polynomial time
on a nondeterministic TM
2) A polynomial‐time verifier for a language is a
deterministic ‐time algorithm such that
iff there exists a certificate such that accepts
Theorem: A language 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 vs. question
Believe , but very far from proving it
Question 1: How can studying specific computational
problems help us get a handle on resolving vs. ?
Question 2: What would allow us to conclude
about specific problems we care about?
Idea: Identify the “hardest” problems in NP
Find such that iff
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
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
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 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/21/2021 CS332 ‐ Theory of Computation 7
Is closed under poly‐time reductions?
If and is in , does that mean is also in ?
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) and
2) Every language is poly‐time reducible to
, i.e., (“ is NP‐hard”)
4/21/2021 CS332 ‐ Theory of Computation 9
Implications of NP‐completeness
Theorem: Suppose is NP‐complete.
Then iff
Proof:
4/21/2021 CS332 ‐ Theory of Computation 10
Implications of NP‐completeness
Theorem: Suppose is NP‐complete.
Then iff
Consequences of being NP‐complete:
1) If you want to show , you just have to show
2) If you want to show , you just have to show
3) If you already believe , then you believe
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:
is NP‐complete
Proof sketch: 1) : Certificate =
nondeterministic guesses made by , verifier checks that
accepts within steps under those guesses.
2) is ‐hard: Let be decided by NTM
running in time The following poly‐time TM
shows :
“On input (an instance of ):
Output | | .”
4/21/2021 CS332 ‐ Theory of Computation 13
Cook‐Levin Theorem
Theorem: (Boolean satisfiability) is NP‐complete
“Proof”: Already know . (Much) harder direction:
Need to show every problem in 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 and , then
(poly‐time reducibility is transitive)
Theorem: If and 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‐CNF Satisfiability)
Definitions:
• A literal either a variable of its negation ,
• A clause is a disjunction (OR) of literals Ex.
• A 3‐CNF is a conjunction (AND) of clauses where each
clause contains exactly 3 literals
Ex. …
4/21/2021 CS332 ‐ Theory of Computation 17
is NP‐complete
Theorem: is NP‐complete
Proof idea: 1) is in NP (why?)
2) Show that
Your classmate suggests the following reduction from to
: “On input , a 3‐CNF formula (an instance of ,
output , which is already an instance of .” Is this
reduction correct?
a) Yes, this is a poly‐time reduction from to
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 to ; it goes in the
wrong direction
4/21/2021 CS332 ‐ Theory of Computation 18
is NP‐complete
Theorem: is NP‐complete
Proof idea: 1) is in NP (why?)
2) Show that
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)
2) Reduce
Proof of 1) The following gives a poly‐time verifier for
𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 𝑆𝐸𝑇
Certificate: Vertices 𝑣 , … , 𝑣
Verifier:
“On input 𝐺,𝑘; 𝑣 , … , 𝑣 , where 𝐺 is a graph, 𝑘 is a natural number,
1. Check that 𝑣 , … 𝑣 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)
2) Reduce
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
𝜑 𝑥 ∨ 𝑥 ∨ 𝑥 ∧ 𝑥 ∨ 𝑥 ∨ 𝑥 ∧ 𝑥 ∨ 𝑥 ∨ 𝑥
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: 𝑂 𝑘 𝑙 which is polynomial in input size
4/21/2021 CS332 ‐ Theory of Computation 25