BU CS 332 – Theory of Computation
Lecture 22:
• NP-Completeness Example • Space Complexity
• Savitch’s Theorem
Mark Bun April 22, 2020
Reading:
Sipser Ch 8.1-8.2
NP-completeness
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”)
Theorem: If 𝐶𝐶 ∈ NP and 𝐵𝐵 ≤p 𝐶𝐶 for some NP-complete language 𝐵𝐵, then 𝐶𝐶 is also NP-complete
4/22/2020 CS332 – Theory of Computation 2
3𝑆𝑆𝐴𝐴𝑆𝑆 (3-CNF Satisfiability) Definition(s):
• A literal either a variable of its negation 𝑥𝑥 , 𝑥𝑥 57
• 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.𝐶𝐶 ∧𝐶𝐶 ∧…∧𝐶𝐶 =
12𝑚𝑚
𝑥𝑥5∨𝑥𝑥7∨𝑥𝑥2 ∧ 𝑥𝑥3∨𝑥𝑥4∨𝑥𝑥1 ∧⋯∧ 𝑥𝑥1∨𝑥𝑥1∨𝑥𝑥1
3𝑆𝑆𝐴𝐴𝑆𝑆 = 𝜑𝜑
Cook-Levin Theorem: 3𝑆𝑆𝐴𝐴𝑆𝑆 is NP-complete
𝜑𝜑isasatisfiable3−CNF
4/22/2020 CS332 – Theory of Computation 3
Some general reduction strategies
Ex. 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆 ≤
and 𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆
• Reduction by simple equivalence
Ex. 𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 ≤ • Gadget reductions
𝑉𝑉𝐼𝐼𝑉𝑉𝑆𝑆𝐼𝐼𝑉𝑉 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉
p
𝑆𝑆𝐼𝐼𝑆𝑆 − 𝐶𝐶𝑂𝑂𝑉𝑉𝐼𝐼𝑉𝑉 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆
CS332 – Theory of Computation 4
• Reduction from special case to general case
Ex. 3𝑆𝑆𝐴𝐴𝑆𝑆 ≤ 4/22/2020
p p
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 5
Independent Set is NP-complete
1) 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆 ∈ NP
2) Reduce 3𝑆𝑆𝐴𝐴𝑆𝑆 ≤p 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝑆𝑆 − 𝑆𝑆𝐼𝐼𝑆𝑆
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 6
• 𝐺𝐺 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
𝜑𝜑= 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥3 ∧ 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥3 ∧ 𝑥𝑥1∨𝑥𝑥2∨𝑥𝑥4
4/22/2020 CS332 – Theory of Computation 7
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: 𝑂𝑂(𝑘𝑘 + 𝑙𝑙2) which is polynomial in input size
4/22/2020 CS332 – Theory of Computation 8
Space Complexity
4/22/2020 CS332 – Theory of Computation 9
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 10
Space analysis
Space complexity of a TM (algorithm) = maximum number of tape cell it uses on a worst-case input
Formally: Let 𝑓𝑓 ∶ N → N. A TM 𝑀𝑀 runs in space 𝑓𝑓(𝑛𝑛) if on everyinput𝑤𝑤∈Σ∗,𝑀𝑀haltson𝑤𝑤usingatmost𝑓𝑓 𝑛𝑛 cells
For nondeterministic machines: Let 𝑓𝑓 ∶ N → N. An NTM 𝐼𝐼 runs in space 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ∗, 𝐼𝐼 halts on 𝑤𝑤 using at most 𝑓𝑓 𝑛𝑛 cells on every computational branch
4/22/2020 CS332 – Theory of Computation 11
Space complexity classes
Let𝑓𝑓∶ N→ N
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/22/2020 CS332 – Theory of Computation 12
Example: Space complexity of SAT
Theorem: 𝑆𝑆𝐴𝐴𝑆𝑆 ∈ SPACE(𝑛𝑛)
Proof: The following deterministic TM decides 𝑆𝑆𝐴𝐴𝑆𝑆 using
linear space
On input 𝜑𝜑 where 𝜑𝜑 is a Boolean formula:
1. For each truth assignment to the variables
𝑥𝑥,…,𝑥𝑥 of𝜑𝜑: 1𝑚𝑚
2. Evaluate 𝜑𝜑 on 𝑥𝑥1, … , 𝑥𝑥𝑚𝑚
3. If any evaluation = 1, accept. Else, reject.
4/22/2020 CS332 – Theory of Computation 13
Example: NFA analysis
Theorem:Let𝐴𝐴𝐴𝐴𝐴𝐴𝑁𝑁𝑁𝑁𝑁𝑁 = 𝐴𝐴 𝐴𝐴isanNFAwith𝐴𝐴 𝐴𝐴 = Σ∗} Then 𝐴𝐴𝐴𝐴𝐴𝐴𝑁𝑁𝑁𝑁𝑁𝑁 ∈ NSPACE(𝑛𝑛).
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 2𝑞𝑞 times where 𝑞𝑞 is the # of states of 𝐴𝐴:
Nondeterministically select 𝑎𝑎 ∈ Σ.
Adjust the markers to simulate all ways for 𝐴𝐴 to read 𝑎𝑎. Accept if at any point none of the markers are on an accept state. Else, reject.
4/22/2020 CS332 – Theory of Computation 14
Example
0,1
1ε203 1
4/22/2020 CS332 – Theory of Computation 15
Space vs. Time
4/22/2020 CS332 – Theory of Computation 16
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 17
Reminder: Configurations
A configuration is a string 𝑢𝑢𝑞𝑞𝑢𝑢 where 𝑞𝑞 ∈ 𝑄𝑄 and 𝑢𝑢, 𝑢𝑢 ∈ Γ∗ • Tape contents = 𝑢𝑢𝑢𝑢 (followed by blanks ⊔)
• Current state = 𝑞𝑞
• Tape head on first symbol of 𝑢𝑢
Example: 101𝑞𝑞5 0111
Start configuration: 𝑞𝑞0𝑤𝑤
Accepting configuration: 𝑞𝑞 = 𝑞𝑞accept Rejecting configuration: 𝑞𝑞 = 𝑞𝑞reject
4/22/2020 CS332 – Theory of Computation 18
Reminder: Configurations
• 𝑘𝑘 states
Consider a TM with
• tape alphabet {0, 1}
• space 𝑓𝑓(𝑛𝑛)
How many configurations are possible when this TM is run on aninput𝑤𝑤∈ 0,1𝑛𝑛?
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 2𝑂𝑂 𝑓𝑓 𝑛𝑛
4/22/2020 CS332 – Theory of Computation 19
Savitch’s Theorem
4/22/2020 CS332 – Theory of Computation 20
Savitch’s Theorem: Deterministic vs. Nondeterministic Space
Theorem: Let 𝑓𝑓 be a function with 𝑓𝑓 𝑛𝑛 ≥ 𝑛𝑛. Then 𝐼𝐼𝑆𝑆𝐼𝐼𝐴𝐴𝐶𝐶𝐼𝐼𝑓𝑓𝑛𝑛 ⊆𝑆𝑆𝐼𝐼𝐴𝐴𝐶𝐶𝐼𝐼 𝑓𝑓𝑛𝑛 2 .
• Let 𝐼𝐼 be an NTM deciding 𝑓𝑓 in space 𝑓𝑓(𝑛𝑛)
Proof idea:
• WeconstructaTM𝑀𝑀deciding𝑓𝑓inspace𝑂𝑂 𝑓𝑓 𝑛𝑛
2 decide whether 𝐼𝐼 can go from 𝑐𝑐1 to 𝑐𝑐2 in ≤ 𝑡𝑡 steps
• Actually solve a more general problem:
• Given configurations 𝑐𝑐 , 𝑐𝑐 of 𝐼𝐼 and natural number 𝑡𝑡,
on some nondeterministic path. • Procedure CANYIELD(𝑐𝑐 , 𝑐𝑐 , 𝑡𝑡)
12
12
4/22/2020 CS332 – Theory of Computation 21
Theorem: Let 𝑓𝑓 be a function with 𝑓𝑓 𝑛𝑛 ≥ 𝑛𝑛. Then 𝐼𝐼𝑆𝑆𝐼𝐼𝐴𝐴𝐶𝐶𝐼𝐼𝑓𝑓𝑛𝑛 ⊆𝑆𝑆𝐼𝐼𝐴𝐴𝐶𝐶𝐼𝐼 𝑓𝑓𝑛𝑛 2 .
• Let 𝐼𝐼 be an NTM deciding 𝑓𝑓 in space 𝑓𝑓(𝑛𝑛) 𝑀𝑀 = “On input 𝑤𝑤:
Savitch’s Theorem
Proof idea:
1. Output the result of CANYIELD(𝑐𝑐1, 𝑐𝑐2, 2𝑑𝑑𝑓𝑓 𝑛𝑛 )” Where CANYIELD(𝑐𝑐 , 𝑐𝑐 , 𝑡𝑡) decides whether 𝐼𝐼 can go from
configuration 𝑐𝑐 to 𝑐𝑐 in ≤ 𝑡𝑡 steps on some nondeterministic
path
4/22/2020
CS332 – Theory of Computation 22
1 122
CANYIELD(𝑐𝑐 , 𝑐𝑐 , 𝑡𝑡) decides whether 𝐼𝐼 can go from configuration
2. 3. 4. 5. 6.
𝑚𝑚𝑚𝑚𝑑𝑑 Run CANYIELD(〈𝑐𝑐1, 𝑐𝑐𝑚𝑚𝑚𝑚𝑑𝑑, 𝑡𝑡/2〉).
Savitch’s Theorem
𝑐𝑐 to 𝑐𝑐 in ≤ 𝑡𝑡 steps on some nondeterministic path: 12
12
CANYIELD(𝑐𝑐1, 𝑐𝑐2, 𝑡𝑡) =
1. If 𝑡𝑡 = 1, accept if 𝑐𝑐1 = 𝑐𝑐2 or 𝑐𝑐1 yields 𝑐𝑐2 in one transition.
Else, reject.
If𝑡𝑡>1,thenforeachconfig𝑐𝑐 of𝐼𝐼with≤𝑓𝑓 𝑛𝑛 cells:
Run CANYIELD(〈𝑐𝑐𝑚𝑚𝑚𝑚𝑑𝑑, 𝑐𝑐2, 𝑡𝑡/2〉).
If both runs accept, accept. Reject.
4/22/2020 CS332 – Theory of Computation 23
Complexity class PSPACE
Definition: PSPACE is the class of languages decidable in
PSPACE = ⋃∞ SPACE(𝑛𝑛𝑘𝑘) 𝑘𝑘=1
polynomial space on a basic single-tape (deterministic) TM
Definition: NPSPACE is the class of languages decidable in polynomial space on a single-tape (nondeterministic) TM
NPSPACE = ⋃∞ NSPACE(𝑛𝑛𝑘𝑘) 𝑘𝑘=1
4/22/2020 CS332 – Theory of Computation 24
1. P⊆NP⊆PSPACE⊆EXP
since 𝑆𝑆𝐼𝐼𝐴𝐴𝐶𝐶𝐼𝐼 𝑓𝑓 𝑛𝑛 ⊆ 𝑆𝑆𝐼𝐼𝑀𝑀𝐼𝐼(2𝑂𝑂(𝑓𝑓 𝑛𝑛 )) EXP
Relationships between complexity classes
2. P ≠ EXP (Monday)
P Which containments N
in (1) are proper?
Unknown!
P
PSPACE=NPSPACE
4/22/2020 CS332 – Theory of Computation
25