BU CS 332 – Theory of Computation
Lecture 23:
• Savitch’s Theorem
• PSPACE-Completeness
• Unconditional Hardness • Course Evaluations
Mark Bun April 27, 2020
Reading:
Sipser Ch 8.1-8.3, 9.1
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/27/2020 CS332 – Theory of Computation 2
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/27/2020 CS332 – Theory of Computation 3
Savitch’s Theorem
4/27/2020 CS332 – Theory of Computation 4
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.
• Design procedure CANYIELD(𝑐𝑐 , 𝑐𝑐 , 𝑡𝑡)
12
4/27/2020 CS332 – Theory of Computation 5
12
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/27/2020
CS332 – Theory of Computation 6
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/27/2020 CS332 – Theory of Computation 7
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/27/2020 CS332 – Theory of Computation 8
1. P⊆NP⊆PSPACE⊆EXP
since 𝑁𝑁𝑁𝑁𝐴𝐴𝑁𝑁𝑁𝑁 𝑓𝑓 𝑛𝑛 ⊆ 𝑇𝑇𝑇𝑇𝑀𝑀𝑁𝑁(2𝑂𝑂(𝑓𝑓 𝑛𝑛 )) EXP
2. P ≠ EXP (Monday)
P Which containments N
Relationships between complexity classes
in (1) are proper?
Unknown!
P
PSPACE=NPSPACE
4/27/2020 CS332 – Theory of Computation
9
PSPACE-Completeness
4/27/2020 CS332 – Theory of Computation 10
What happens in a world where P ≠ PSPACE? Even more believable than P ≠ NP, but still(!) very far from
proving it
Question: What would P ≠ PSPACE allow us to conclude about problems we care about?
PSPACE-completeness: Find the “hardest” problems in PSPACE Find𝐿𝐿∈PSPACEsuchthat𝐿𝐿∈P iff P=PSPACE
4/27/2020 CS332 – Theory of Computation 11
Reminder: 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”)
4/27/2020 CS332 – Theory of Computation 12
PSPACE-completeness
Definition: A language 𝐵𝐵 is PSPACE-complete if
1) 𝐵𝐵 ∈ PSPACE, and
2) Every language 𝐴𝐴 ∈ PSPACE is poly-time reducible to
𝐵𝐵, i.e., 𝐴𝐴 ≤p 𝐵𝐵 (“𝐵𝐵 is PSPACE-hard”)
4/27/2020 CS332 – Theory of Computation 13
A PSPACE-complete problem: TQBF
“Is a fully quantified logical formula true?”
• Boolean variable: Variable that can take on the value
true/false (encoded as 0/1)
• Boolean operations: ∧ AND , ∨ OR , ¬ (NOT)
operations. Ex: (𝑥𝑥 ∨ 𝑥𝑥 ) ∧ 𝑥𝑥 123
• Boolean formula: Expression made of Boolean variables and
• Fully quantified Boolean formula: Boolean formula with all variables quantified (∀, ∃) Ex: ∀𝑥𝑥 ∃𝑥𝑥 ∀𝑥𝑥 (𝑥𝑥 ∨ 𝑥𝑥 ) ∧ 𝑥𝑥
132123
• Every fully quantified Boolean formula is either true or false
• 𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇 = 𝜑𝜑 𝜑𝜑 is a true fully quantified formula
4/27/2020 CS332 – Theory of Computation 14
Theorem: TQBF is PSPACE-complete
Need to prove two things…
1) 𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇 ∈ PSPACE
2) Every problem in PSPACE is poly-time reducible to 𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇 (𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇 is PSPACE-hard)
4/27/2020 CS332 – Theory of Computation 15
1) TQBF is in PSPACE
𝑇𝑇 = “On input 〈𝜑𝜑〉,
where 𝜑𝜑 is a fully quantified Boolean formula:
1. If 𝜑𝜑 has no quantifiers, it has only constants (and no variables). Evaluate 𝜑𝜑.
If true, accept; else, reject.
2. If 𝜑𝜑 is of the form ∃𝑥𝑥 𝜓𝜓, recursively call 𝑇𝑇
on 𝜓𝜓 with 𝑥𝑥 = 0 and then on 𝜓𝜓 with 𝑥𝑥 = 1.
If either call accepts, accept; else, reject. 3. If 𝜑𝜑 is of the form ∀𝑥𝑥 𝜓𝜓, recursively call 𝑇𝑇
on 𝜓𝜓 with 𝑥𝑥 = 0 and then on 𝜓𝜓 with 𝑥𝑥 = 1. If both calls accept, accept; else, reject.’’
•If𝑛𝑛istheinputlength,𝑇𝑇usesspace𝑂𝑂 𝑛𝑛 . 4/27/2020 CS332 – Theory of Computation
16
2) TQBF is PSPACE-hard
Theorem: Every language 𝐴𝐴 ∈ PSPACE is poly-time reducible to 𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇
Let 𝐴𝐴 ∈ PSPACE be decided by a poly-space deterministic TM 𝑀𝑀. Using proof of Cook-Levin Theorem,
Proof idea:
𝑀𝑀 accepts input 𝑤𝑤 ⟺ formula 𝜑𝜑𝑀𝑀,𝑤𝑤 is true
Using idea of Savitch’s Theorem, replace 𝜑𝜑𝑀𝑀,𝑤𝑤 with a quantified formula of poly-size that can be computed in poly-time
4/27/2020 CS332 – Theory of Computation 17
Unconditional Hardness
4/27/2020 CS332 – Theory of Computation 18
Hardness results so far
•IfP≠NP,then3𝑁𝑁𝐴𝐴𝑇𝑇 ∉𝑁𝑁 •IfP≠PSPACE,then𝑇𝑇𝑇𝑇𝐵𝐵𝑇𝑇 ∉𝑁𝑁
Question: Are there decidable languages that we can show are not in 𝑁𝑁?
4/27/2020 CS332 – Theory of Computation 19
Diagonalization redux
TM 𝑀𝑀
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
4/27/2020
CS332 – Theory of Computation 20
…
Diagonalization redux
TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )?
𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4
𝐷𝐷( 𝐷𝐷 )? YNYY
N
Y
N
N
Y
N
Y
Y
Y
Y
N
N
…
𝑁𝑁𝐴𝐴 𝐷𝐷 = 𝑀𝑀 𝑀𝑀isaTMthatdoesnotacceptinput 𝑀𝑀 } 𝑁𝑁𝐴𝐴TM = 𝑀𝑀 𝑀𝑀isaTMthatdoesnotacceptinput 𝑀𝑀
TM,𝐸𝐸𝐸𝐸𝐸𝐸 within 2| 𝑀𝑀 | steps}
4/27/2020 CS332 – Theory of Computation 21
…
An explicit undecidable language
𝑀𝑀isaTMthat
• In EXP: Simulate 𝑀𝑀 on input 𝑀𝑀 for 2| 𝑀𝑀 | steps and flip
•Theorem:𝐿𝐿=𝑁𝑁𝐴𝐴TM,𝐸𝐸𝐸𝐸𝐸𝐸 = 𝑀𝑀
does not accept input 𝑀𝑀 within 2| 𝑀𝑀 | steps}
is in EXP, but not in P Proof:
its decision
• Not in P: Suppose for contradiction that 𝐷𝐷 decides 𝐿𝐿 in
time 𝑛𝑛𝑘𝑘
4/27/2020 CS332 – Theory of Computation 22
Time and space hierarchy theorems
• For any* function 𝑓𝑓 𝑛𝑛 ≥ 𝑛𝑛 log 𝑛𝑛 , a language exists that is decidable in 𝑓𝑓(𝑛𝑛) time, but not in 𝑜𝑜 𝑓𝑓 𝑛𝑛 time.
log 𝑓𝑓 𝑛𝑛
• For any* function 𝑓𝑓 𝑛𝑛 ≥ 𝑛𝑛 log 𝑛𝑛 , a language exists that
is decidable in 𝑓𝑓(𝑛𝑛) space, but not in 𝑜𝑜 𝑓𝑓(𝑛𝑛) space.
*time constructible and space constructible, respectively
4/27/2020 CS332 – Theory of Computation 23
recognizable decidable
EXPSPACE EXPTIME PSPACE=NPSPACE
NP
P
CFL regular
coNP
4/27/2020
CS332 – Theory of Computation 24
Course evaluations
https://bu.campuslabs.com/courseeval
4/27/2020 CS332 – Theory of Computation 25