BU CS 332 – Theory of Computation
Lecture 21:
• NP‐Completeness
• Cook‐Levin Theorem • Reductions
Reading:
Sipser Ch 7.3‐7.5
Mark Bun April 15, 2020
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
iff there exists a string
‐time algorithm such that such that accepts
Theorem: A language verifier for
iff there is a polynomial‐time
4/15/2020
CS332 ‐ Theory of Computation 2
Examples of languages: SAT
“Is there an assignment to the variables in a logical
formula that make it evaluate to ?”
• Boolean variable: Variable that can take on the value / (encoded as 0/1)
• Boolean operations:
• Boolean formula: Expression made of Boolean variables
and operations. Ex:
• 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
languages: SAT
Ex: Ex:
Satisfiable? Satisfiable?
Claim:
4/15/2020
CS332 ‐ Theory of Computation
4
Examples of languages: TSP
“Given a list of cities and distances between them, is
there a ‘short’ tour of all of the cities?”
More precisely: Given
• A number of cities
• A function giving the distance between each pair of cities
• A distance bound
4/15/2020 CS332 ‐ Theory of Computation 5
EXP
NP
EXP
vs.
Question: Does ?
Philosophically: Can every problem with an efficiently verifiable solution also be solved efficiently?
A central problem in mathematics and computer science
P
P = NP
If PNP 4/15/2020
If P=NP
CS332 ‐ Theory of Computation 6
A world where
• 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
• 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:
4/15/2020 CS332 ‐ Theory of Computation
8
NP‐Completeness
4/15/2020 CS332 ‐ Theory of Computation 9
What about a world where
Believe this to be true, but very far from proving it
implies that there is a problem in which cannot be solved in polynomial time, but it might not be a useful one
Question: What would allow us to conclude about problems we care about?
Idea: Identify the “hardest” problems in NP Find such that iff
4/15/2020 CS332 ‐ Theory of Computation 10
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/15/2020 CS332 ‐ Theory of Computation 11
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/15/2020 CS332 ‐ Theory of Computation
12
∗∗
Implications of poly‐time reducibility
Theorem: If
and then
Proof: Let decide in poly time:
in poly time, and let be a poly‐ time reduction from to . The following TM decides
4/15/2020
CS332 ‐ Theory of Computation 13
NP‐completeness
Definition: A language is NP‐complete if 1) and
4/15/2020
CS332 ‐ Theory of Computation 14
2) Every language is poly‐time reducible to , i.e., (“ is NP‐hard”)
Implications of NP‐completeness
Theorem: Suppose Then
is NP‐complete. iff
Proof:
4/15/2020
CS332 ‐ Theory of Computation 15
Implications of NP‐completeness
Theorem: Suppose Then
is NP‐complete. iff
Consequences of
being NP‐complete:
1) 2) 3)
If you want to show If you want to show If you already believe
, you just have to show , you just have to show
4/15/2020 CS332 ‐ Theory of Computation 16
, then you believe
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 . Need to show every
problem in 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 and , then (poly‐time reducibility is transitive)
Theorem: If language , then
and for some NP‐complete 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!
4/15/2020
CS332 ‐ Theory of Computation
20
INDEPENDENT SET
DIR-HAM-CYCLE
GRAPH 3-COLOR
SUBSET-SUM
VERTEX COVER
HAM-CYCLE
PLANAR 3-COLOR
SCHEDULING
SET COVER
TSP
SAT 3SAT
by definition of NP‐completeness
(3‐CNF Satisfiability)
Definition(s):
• 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/15/2020 CS332 ‐ Theory of Computation 21
is NP‐complete
Theorem: is NP‐complete Proof idea: 1) is in NP (why?)
2) Show that
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