BU CS 332 – Theory of Computation
Lecture 22:
• NP‐Completeness Example • Space Complexity
• Savitch’s Theorem
Reading:
Sipser Ch 8.1‐8.2
Mark Bun April 22, 2020
NP‐completeness
Definition: A language is NP‐complete if 1) and
2) Every language
is poly‐time reducible to is NP‐hard”)
Theorem: If language , then
for some NP‐complete is also NP‐complete
4/22/2020
CS332 ‐ Theory of Computation 2
, i.e.,
(“ and
(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. …
Cook‐Levin Theorem: is NP‐complete
4/22/2020 CS332 ‐ Theory of Computation 3
4/22/2020 CS332 ‐ Theory of Computation 4
Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 𝑆𝐸𝑇 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅
and 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 𝑆𝐸𝑇 • Reduction from special case to general case
Ex. 𝑉𝐸𝑅𝑇𝐸𝑋 𝐶𝑂𝑉𝐸𝑅 𝑆𝐸𝑇 𝐶𝑂𝑉𝐸𝑅 • Gadget reductions
Ex. 3𝑆𝐴𝑇 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 𝑆𝐸𝑇
4/22/2020 CS332 ‐ Theory of Computation 5
Independent Set
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
4/22/2020 CS332 ‐ Theory of Computation 6
Independent Set is NP‐complete
1)
2) Reduce
Proof. “On input 𝜑 , where 𝜑 is a 3CNF formula,
1.
Construct graph 𝐺 from 𝜑
2.
Output 𝐺, 𝑘 , where 𝑘 is the number of clauses in 𝜑.”
4/22/2020 CS332 ‐ Theory of Computation 7
• 𝐺 contains 3 vertices for each clause, one for each literal. • Connect 3 literals in a clause in a triangle.
• Connect literal to each of its negations.
Example of the reduction
𝜑 𝑥∨𝑥∨𝑥 ∧ 𝑥∨𝑥∨𝑥 ∧ 𝑥∨𝑥∨𝑥
4/22/2020 CS332 ‐ Theory of Computation 8
Proof of correctness for reduction
Let 𝑘 = # clauses and 𝑙 = # literals in 𝜑
Claim: 𝜑 is satisfiable iff 𝐺 has an ind. set of size 𝑘
⟹ Given a satisfying assignment, select one literal from each triangle. This is an ind. set of size 𝑘
⟸ Let 𝑆 be an ind. set 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 satisfied
Runtime: 𝑂𝑘 𝑙 which is polynomial in input size
4/22/2020 CS332 ‐ Theory of Computation 9
Space Complexity
4/22/2020 CS332 ‐ Theory of Computation 10
Complexity measures we’ve studied so far
• Deterministic time TIME
• Nondeterministic time NTIME • Classes P, NP
Many other resources of interest:
Space (memory), randomness, parallel runtime / #processors, quantum entanglement, interaction, communication, …
4/22/2020 CS332 ‐ Theory of Computation 11
Space analysis
Space complexity of a TM (algorithm) = maximum number of tape cell it uses on a worst‐case input
Formally: Let ∗ . A TM every input , halts on
runs in space
if on cells
For nondeterministic machines:
runs in space
,
cells on every computational branch
using at most
4/22/2020
CS332 ‐ Theory of Computation 12
Let ∗ if on every input
. An NTM halts on
using at most
Space complexity classes
Let
A language
tape (deterministic) TM
if there exists a basic single‐ that
1) Decides , and 2) Runs in space
A language
tape nondeterministic TM
if there exists a single‐ that
1) Decides , and 2) Runs in space
4/22/2020 CS332 ‐ Theory of Computation 13
Example: Space complexity of SAT
Theorem:
Proof: The following deterministic TM decides linear space
using
On input where is a Boolean formula:
1. For each truth assignment to the variables
of:
2. Evaluate on
3. If any evaluation , accept. Else, reject.
4/22/2020 CS332 ‐ Theory of Computation 14
Example: NFA analysis
Theorem: Let
Then
Proof: The following NTM decides
∗ in linear space
On input where is an NTM:
1. 2. 3. 4. 5.
Place a marker on the start state of .
Repeat times where is the # of states of :
Nondeterministically select .
.
Adjust the markers to simulate all ways for
Accept if at any point none of the markers are on an accept state. Else, reject.
4/22/2020 CS332 ‐ Theory of Computation 15
to read
Example
0,1
1ε203 1
4/22/2020 CS332 ‐ Theory of Computation 16
Space vs. Time
4/22/2020 CS332 ‐ Theory of Computation 17
Space vs. Time
How about the opposite direction? Can low‐space algorithms be simulated by low‐time algorithms?
4/22/2020 CS332 ‐ Theory of Computation 18
Reminder: Configurations
A configuration is a string where
• Tape contents = (followed by blanks • Current state =
• Tape head on first symbol of
and )
∗
Example:
Start configuration: Accepting configuration: = Rejecting configuration: =
4/22/2020 CS332 ‐ Theory of Computation
19
Reminder: Configurations
Consider a TM with
• states
• tape alphabet
• space
How many configurations are possible when this TM is run on
an input
Observation: If a TM enters the same configuration twice when run on input it loops forever
Corollary: A TM running in space also runs in time
4/22/2020 CS332 ‐ Theory of Computation 20
Savitch’s Theorem
4/22/2020 CS332 ‐ Theory of Computation 21
Savitch’s Theorem: Deterministic vs. Nondeterministic Space
Theorem: Let be a function with . Then
4/22/2020 CS332 ‐ Theory of Computation
22