PowerPoint Presentation
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
𝐴𝐴 ≤p 𝐵𝐵
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) 𝐵𝐵 ∈ NP, and
2) Every language 𝐴𝐴 ∈ NP is poly-time reducible to
𝐵𝐵, i.e., 𝐴𝐴 ≤p 𝐵𝐵 (“𝐵𝐵 is NP-hard”)
4/26/2021 CS332 – Theory of Computation 3
The usual way to prove NP-completeness
Theorem:
If
1) 𝐶𝐶 ∈ NP, and
2) There is an NP-complete language 𝐵𝐵 such that
𝐵𝐵 ≤p 𝐶𝐶
then 𝐶𝐶 is NP-complete.
4/26/2021 CS332 – Theory of Computation 4
Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆 ≤p 𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉
𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆
• Reduction from special case to general case
Ex. 𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉 ≤p 𝑆𝑆𝑆𝑆𝑆𝑆 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉
3𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 𝑆𝑆𝐴𝐴𝑆𝑆
• “Gadget” reductions
Ex. 𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 3𝑆𝑆𝐴𝐴𝑆𝑆
3𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆
4/26/2021 CS332 – Theory of Computation 5
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
Last time: 3𝑆𝑆𝐴𝐴𝑆𝑆 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) 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆 ∈ 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/26/2021 CS332 – Theory of Computation 8
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/26/2021 CS332 – Theory of Computation 9
Example of the reduction
4/26/2021 CS332 – Theory of Computation 10
𝜑𝜑 = 𝑥𝑥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 arbitrarily
• Truth assignment is consistent and all clauses are satisfied
Runtime: 𝑂𝑂(𝑘𝑘 + 𝑙𝑙2) which is polynomial in input size
4/26/2021 CS332 – Theory of Computation 11
Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆 ≤p 𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉
𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆
• Reduction from special case to general case
Ex. 𝑉𝑉𝑆𝑆𝑉𝑉𝑆𝑆𝑆𝑆𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉 ≤p 𝑆𝑆𝑆𝑆𝑆𝑆 − 𝐶𝐶𝑂𝑂𝑉𝑉𝑆𝑆𝑉𝑉
3𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 𝑆𝑆𝐴𝐴𝑆𝑆
• “Gadget” reductions
Ex. 𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 3𝑆𝑆𝐴𝐴𝑆𝑆
3𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼 − 𝑆𝑆𝑆𝑆𝑆𝑆
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 ≤p 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 ≤p 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 ≤p 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 𝐴𝐴 ∈ SPACE(𝑓𝑓(𝑛𝑛)) if there exists a basic single-
tape (deterministic) TM 𝑀𝑀 that
1) Decides 𝐴𝐴, and
2) Runs in space 𝑂𝑂(𝑓𝑓(𝑛𝑛))
A language 𝐴𝐴 ∈ NSPACE(𝑓𝑓(𝑛𝑛)) 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
TIME 𝑓𝑓 𝑛𝑛 ⊆ NTIME 𝑓𝑓 𝑛𝑛
⊆ SPACE 𝑓𝑓 𝑛𝑛 ⊆ NSPACE 𝑓𝑓 𝑛𝑛
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
2𝑂𝑂 𝑓𝑓 𝑛𝑛
4/26/2021 CS332 – Theory of Computation 21
Savitch’s Theorem: Deterministic vs.
Nondeterministic Space
Theorem: Let 𝑓𝑓 be a function with 𝑓𝑓 𝑛𝑛 ≥ log𝑛𝑛. Then
NSPACE 𝑓𝑓 𝑛𝑛 ⊆ SPACE 𝑓𝑓 𝑛𝑛
2
.
4/26/2021 CS332 – Theory of Computation 22
Complexity class PSPACE
Definition: PSPACE is the class of languages decidable in
polynomial space on a basic single-tape (deterministic) TM
PSPACE = ⋃𝑘𝑘=1
∞ SPACE(𝑛𝑛𝑘𝑘)
Definition: NPSPACE is the class of languages decidable in
polynomial space on a single-tape (nondeterministic) TM
NPSPACE = ⋃𝑘𝑘=1
∞ NSPACE(𝑛𝑛𝑘𝑘)
4/26/2021 CS332 – Theory of Computation 23
Relationships between complexity classes
4/26/2021 CS332 – Theory of Computation 24
1. P ⊆ NP ⊆ PSPACE ⊆ EXP
since SPACE 𝑓𝑓 𝑛𝑛 ⊆ TIME(2𝑂𝑂(𝑓𝑓 𝑛𝑛 ))
2. P ≠ EXP
(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
https://bu.campuslabs.com/courseeval
BU CS 332 – Theory of Computation
Polynomial-time reducibility
NP-completeness
The usual way to prove NP-completeness
Some general reduction strategies
3𝑆𝐴𝑇 (3-CNF Satisfiability)
Independent Set
Independent Set is NP-complete
Independent Set is NP-complete
Example of the reduction
Proof of correctness for reduction
Some general reduction strategies
Vertex Cover
Independent Set and Vertex Cover
INDEPENDENT SET reduces to VERTEX COVER
INDEPENDENT SET reduces to VERTEX COVER
VERTEX COVER reduces to INDEPENDENT SET
A Brief Tour of Space (Complexity)
Space analysis
Space complexity classes
Space vs. Time
Savitch’s Theorem: Deterministic vs. Nondeterministic Space
Complexity class PSPACE
Relationships between complexity classes
Course Evaluations