CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

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