Microsoft PowerPoint – CS332-Lec24-ann
BU CS 332 – Theory of Computation
Lecture 24:
• More NP‐completeness
• Space complexity (?)
Reading:
Sipser Ch 7.4‐7.5,
8.1‐8.2
Mark Bun
April 26, 2021
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/26/2021 CS332 ‐ Theory of Computation 2
NP‐completeness
“The hardest languages in NP”
Definition: A language is NP‐complete if
1) and
2) Every language is poly‐time reducible to
, i.e., (“ is NP‐hard”)
4/26/2021 CS332 ‐ Theory of Computation 3
The usual way to prove NP‐completeness
Theorem:
If
1) and
2) There is an NP‐complete language such that
then is NP‐complete.
4/26/2021 CS332 ‐ Theory of Computation 4
Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝑁𝐷 𝑆𝐸𝑇 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅
𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝐼𝑁𝐷 𝑆𝐸𝑇
• Reduction from special case to general case
Ex. 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝑆𝐸𝑇 𝐶𝑂𝑉𝐸𝑅
3𝑆𝐴𝑇 𝑆𝐴𝑇
• “Gadget” reductions
Ex. 𝑆𝐴𝑇 3𝑆𝐴𝑇
3𝑆𝐴𝑇 𝐼𝑁𝐷 𝑆𝐸𝑇
4/26/2021 CS332 ‐ Theory of Computation 5
(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. …
Last time: is NP‐complete
4/26/2021 CS332 ‐ Theory of Computation 6
Independent Set
4/26/2021 CS332 ‐ Theory of Computation 7
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
1
2
3
4
5
6
Which of the following are
independent sets in this graph?
a) 1
b) 1, 5
c) 2, 3, 6
d) 3, 4, 6
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/26/2021 CS332 ‐ Theory of Computation 8
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/26/2021 CS332 ‐ Theory of Computation 9
Example of the reduction
4/26/2021 CS332 ‐ Theory of Computation 10
𝜑 𝑥 ∨ 𝑥 ∨ 𝑥 ∧ 𝑥 ∨ 𝑥 ∨ 𝑥 ∧ 𝑥 ∨ 𝑥 ∨ 𝑥
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 arbitrarily
• Truth assignment is consistent and all clauses are satisfied
Runtime: 𝑂 𝑘 𝑙 which is polynomial in input size
4/26/2021 CS332 ‐ Theory of Computation 11
Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝑁𝐷 𝑆𝐸𝑇 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅
𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝐼𝑁𝐷 𝑆𝐸𝑇
• Reduction from special case to general case
Ex. 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝑆𝐸𝑇 𝐶𝑂𝑉𝐸𝑅
3𝑆𝐴𝑇 𝑆𝐴𝑇
• “Gadget” reductions
Ex. 𝑆𝐴𝑇 3𝑆𝐴𝑇
3𝑆𝐴𝑇 𝐼𝑁𝐷 𝑆𝐸𝑇
4/26/2021 CS332 ‐ Theory of Computation 12
Vertex Cover
Given an undirected graph 𝐺, a vertex cover in 𝐺 is a subset of
nodes which includes at least one endpoint of every edge.
𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 = { 𝐺,𝑘 ∣ 𝐺 is an undirected graph which has a
vertex cover with 𝑘 vertices}
4/26/2021 CS332 ‐ Theory of Computation 13
1
2
3
4
5
6
Which of the following are vertex
covers in this graph?
a) 1
b) 1, 6
c) 1, 2, 5
d) 1, 2, 5, 6
Independent Set and Vertex Cover
Claim. 𝑆 is an independent set iff 𝑉 ∖ 𝑆 is a vertex cover.
⟹ Let 𝑆 be any independent set.
• Consider an arbitrary edge 𝑢, 𝑣 .
• 𝑆 is independent ⟹𝑢 𝑆 or 𝑣 𝑆 ⟹ 𝑢 𝑉 ∖ 𝑆 or 𝑣 𝑉 ∖ 𝑆.
• Thus, 𝑉 ∖ 𝑆 covers 𝑢, 𝑣 .
⟸ Let 𝑉 ∖ 𝑆 be any vertex cover.
• Consider two nodes 𝑢 𝑆 and 𝑣 𝑆.
• Then 𝑢, 𝑣 𝐸 since 𝑉 ∖ 𝑆 is a vertex cover.
• Thus, no two nodes in 𝑆 are joined by an edge ⟹𝑆 is an independent set.
4/26/2021 CS332 ‐ Theory of Computation 14
1
2
3
4
5
6
INDEPENDENT SET reduces to VERTEX COVER
Theorem. IND‐SET VERTEX‐COVER.
What do we need to do to prove this theorem?
a) Construct a poly‐time nondet. TM deciding IND‐SET
b) Construct a poly‐time deterministic TM deciding IND‐SET
c) Construct a poly‐time nondet. TM mapping instances of IND‐
SET to instances of VERTEX‐COVER
d) Construct a poly‐time deterministic TM mapping instances of
IND‐SET to instances of VERTEX‐COVER
e) Construct a poly‐time nondet. TM mapping instances of
VERTEX‐COVER to instances of IND‐SET
f) Construct a poly‐time deterministic TM mapping instances of
VERTEX‐COVER to instances of IND‐SET
4/26/2021 CS332 ‐ Theory of Computation 15
INDEPENDENT SET reduces to VERTEX COVER
Theorem. IND‐SET VERTEX‐COVER.
Proof. The following TM computes the reduction.
“On input , where is an undirected graph and is an
integer,
1. Output where is the number of nodes in ”
Correctness:
• has an independent set of size at least iff it has a vertex
cover of size at most .
Runtime:
• Reduction runs in linear time.
4/26/2021 CS332 ‐ Theory of Computation 16
VERTEX COVER reduces to INDEPENDENT SET
Theorem. VERTEX‐COVER IND‐SET
Proof. The following TM computes the reduction.
“On input , where is an undirected graph and is an
integer,
1. Output where is the number of nodes in ”
Correctness:
• has a vertex cover of size at most iff it has an
independent set of size at least .
Runtime:
• Reduction runs in linear time.
4/26/2021 CS332 ‐ Theory of Computation 17
A Brief Tour of Space
(Complexity)
4/26/2021 CS332 ‐ Theory of Computation 18
Space analysis
Space complexity of a TM (algorithm) = maximum number
of tape cells it uses on a worst‐case input
Formally: Let . A TM runs in space if on
every input ∗, halts on using at most cells
For nondeterministic machines: Let . An NTM
runs in space if on every input ∗, halts on
using at most cells on every computational branch
4/26/2021 CS332 ‐ Theory of Computation 19
Space complexity classes
Let
A language if there exists a basic single‐
tape (deterministic) TM that
1) Decides , and
2) Runs in space
A language if there exists a single‐
tape nondeterministic TM that
1) Decides , and
2) Runs in space
4/26/2021 CS332 ‐ Theory of Computation 20
Space vs. Time
How about the opposite direction? Can low‐space
algorithms be simulated by low‐time algorithms?
Theorem: A TM running in space also runs in time
4/26/2021 CS332 ‐ Theory of Computation 21
Savitch’s Theorem: Deterministic vs.
Nondeterministic Space
Theorem: Let be a function with . Then
4/26/2021 CS332 ‐ Theory of Computation 22
Complexity class
Definition: is the class of languages decidable in
polynomial space on a basic single‐tape (deterministic) TM
Definition: is the class of languages decidable in
polynomial space on a single‐tape (nondeterministic) TM
4/26/2021 CS332 ‐ Theory of Computation 23
Relationships between complexity classes
4/26/2021 CS332 ‐ Theory of Computation 24
since
(via time hierarchy)
Which containments
in (1) are proper?
Unknown!
PSPACE=NPSPACE
EXP
NP
P
Course Evaluations
bu.campuslabs.com/courseeval
4/26/2021 CS332 ‐ Theory of Computation 25