BU CS 332 – Theory of Computation
Lecture 23:
• Savitch’s Theorem
• PSPACE‐Completeness
• Unconditional Hardness • Course Evaluations
Reading:
Sipser Ch 8.1‐8.3, 9.1
Mark Bun April 27, 2020
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/27/2020
CS332 ‐ Theory of Computation 2
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/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 Proof idea:
• Let be an NTM deciding in space
• We construct a TM deciding in space
• Actually solve a more general problem:
• Given configurations of and natural number
,
decide whether can go from to in on some nondeterministic path.
steps
• Design procedure CANYIELD
4/27/2020 CS332 ‐ Theory of Computation
5
Savitch’s Theorem
Theorem: Let be a function with
. Then
Proof idea:
• Let be an NTM deciding in space = “On input :
1. Output the result of CANYIELD
” can go from
where CANYIELD configuration to path
in
decides whether
steps on some nondeterministic
4/27/2020
CS332 ‐ Theory of Computation 6
1.
If
Else, reject.
2. 3. 4. 5. 6.
If
then for each config Run CANYIELD( Run CANYIELD(
of with cells: ).
Savitch’s Theorem
CANYIELD
decides whether can go from configuration steps on some nondeterministic path:
to in CANYIELD
=
accept if or yields in one transition.
If both runs accept, accept Reject.
4/27/2020 CS332 ‐ Theory of Computation
7
).
Complexity class
Definition: is the class of languages decidable in polynomial space on a basic single‐tape (deterministic) TM
is the class of languages decidable in polynomial space on a single‐tape (nondeterministic) TM
Definition:
4/27/2020
CS332 ‐ Theory of Computation 8
Relationships between complexity classes
since
(Monday)
EXP PSPACE=NPSPACE
Which containments NP in (1) are proper?
P
Unknown!
4/27/2020 CS332 ‐ Theory of Computation
9
PSPACE‐Completeness
4/27/2020 CS332 ‐ Theory of Computation 10
What happens in a world where ? Even more believable than , but still(!) very far from
proving it
Question: What would allow us to conclude about problems we care about?
PSPACE‐completeness: Find the “hardest” problems in PSPACE Find such that iff
4/27/2020 CS332 ‐ Theory of Computation 11
Reminder: NP‐completeness
Definition: A language is NP‐complete if 1) and
4/27/2020
CS332 ‐ Theory of Computation 12
2) Every language is poly‐time reducible to , i.e., (“ is NP‐hard”)
PSPACE‐completeness
Definition: A language 1) and 2) Every language
is PSPACE‐complete if
is poly‐time reducible to
4/27/2020
CS332 ‐ Theory of Computation 13
, i.e.,
(“ is PSPACE‐hard”)
A PSPACE‐complete problem: TQBF
“Is a fully quantified logical formula ?”
• Boolean variable: Variable that can take on the value
•
/ (encoded as 0/1)
• Boolean operations:
• Boolean formula: Expression made of Boolean variables and
operations. Ex:
• Fully quantified Boolean formula: Boolean formula with all
variables quantified ( ) Ex:
• Every fully quantified Boolean formula is either true or false
4/27/2020 CS332 ‐ Theory of Computation 14
Theorem: TQBF is PSPACE‐complete
Need to prove two things…
1)
2) Every problem in is poly‐time reducible to ( is PSPACE‐hard)
4/27/2020
CS332 ‐ Theory of Computation 15
1) TQBF is in PSPACE
𝑇 “Oninput , 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 and then on with
If either call accepts, accept; else, reject. on with and then on with
. .
3. If is of the form , recursively call
If both calls accept, accept; else, reject.’’
• If
4/27/2020 CS332 ‐ Theory of Computation
is the input length, uses space
16
2) TQBF is PSPACE‐hard
Theorem: Every language is poly‐time reducible to
Proof idea:
Let be decided by a poly‐space deterministic TM . Using proof of Cook‐Levin Theorem,
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
• If , then
• If , then
Question: Are there decidable languages that we can show are not in ?
4/27/2020
CS332 ‐ Theory of Computation 19
…
Diagonalization redux
TM 𝑀
𝑀 𝑀 𝑀 𝑀
4/27/2020
CS332 ‐ Theory of Computation 20
…
Diagonalization redux
TM𝑀 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ?
𝐷 𝐷 ?
𝑀 𝑀 𝑀 𝑀
Y N Y Y … NNYY
𝐷
,
||
4/27/2020
CS332 ‐ Theory of Computation
21
YYYN NNYN
An explicit undecidable language
• Theorem:
is in , but not in
Proof:
,
||
• In : Simulate on input for | | steps and flip its decision
• Not in : Suppose for contradiction that decides in time
4/27/2020 CS332 ‐ Theory of Computation
22
Time and space hierarchy theorems
• For any* function is decidable in
a language exists that time, but not in time.
• For any* function is decidable in
a language exists that space, but not in space.
*time constructible and space constructible, respectively
4/27/2020 CS332 ‐ Theory of Computation 23
4/27/2020
CS332 ‐ Theory of Computation 24
recognizable decidable
EXPSPACE EXPTIME PSPACE=NPSPACE
NP
coNP
P
CFL regular
Course evaluations
https://bu.campuslabs.com/courseeval
4/27/2020 CS332 ‐ Theory of Computation 25