COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Space Complexity
Copyright By PowCoder代写 加微信 powcoder
This lecture covers Chapter 11 of HMU: Other Complexity Classes
The classes PS and NPS Relationship to other classes Savitch’s Theorem Quantified Boolean Formulae PSpace completeness
Additional Reading: Chapter 11 of HMU.
Polynomial Space
Definition 10.1
A Turing machine M is polyspace bounded if there is a polynomial p so that M never uses more than p(|w|) tape cells when started with input w.
For deterministic machines, this refers to the unique computation path
For non-deterministic machines, this refers to all computation paths starting with
input w. Definition 10.2
The class PS = PSPACE is the class of languages L such that L = L(M) for a polyspace bounded deterministic Turing machine.
The class NPS = NPSPACE is the class of languages L such that L = L(M) for a polyspace bounded nondeterministic Turing machine.
Example ALLNFA
ALLNFA ={{⟨A⟩|AisanNFAandL(A)=Σ∗}
Currently, it’s known neither whether ALLNFA ∈ NP nor whether ALLNFA ∈ co − NP.
NPSPACE Algorithm for ALLcNFA
M = “On input ⟨A⟩, where A = (Q,Σ,δ,q0,F) is an NFA:
Place a marker on q0. If q0 ∈/ F, accept.
Repeat 2|Q| times:
1 Let m ⊆ Q be the positions of markers.
2 Pick any a ∈ Σ and change m to q∈m δ(q,a).
3 Ifm∩F =∅,accept.
M may use exponential time but linear space only.
2|Q| iterations are needed to ensure we can reach all possible patterns of markers on states.
Hence ALLcNFA ∈ NPSPACE.
Q. Why didn’t we introduce coNSPACE?
Relationship to Other Classes
Easy Inclusions
P ⊆ PSPACE and NP ⊆ NPSPACE (you cannot use more than polynomially many cells in polynomial time).
Unknown Inclusions
We don’t know whether P = PSPACE or NP = PSPACE. Inclusions we will see
PSPACE = NPSPACE
this is remarkable, as we don’t know whether P = NP.
Exponential Time
Definition 10.3
A deterministic or non-deterministic Turing machine runs in exponential time if it terminates in at most cp(|w|) steps for a constant c and polynomial p.
EXP is the class of languages L for which L = L(M) for an exptime deterministic Turing machine.
NEXP is the class of languages L for which L = L(M) for a nondeterministic exponential time Turing machine.
More Inclusions
P ⊆ NP ⊆ PSPACE ⊆ EXP
NP ⊆ PSPACE follows once we have shown that NPSPACE = PSPACE
PSPACE ⊆ EXP needs to be proved
We know that P EXP, so that one inclusion is proper But we don’t know which …
PSPACE vs EXP
Theorem 10.4
PSPACE ⊆ EXP Main Idea
A polyspace bounded machine only has cp(n) different ID’s. count up to cp(n) – exponentially many steps
must surely have repeated an ID by then
Proof PSPACE ⊆ EXP
Assume that a TM M only uses p(n) space, and has semi-infinite tape. M has s ×p(n)×tp(n) many ID’s:
s are the states, p(n) are the different head positions, tp(n) is tape contents.
We have (t + 1)p(n)+1 ≥ p(n)tp(n)
…ands=(t+1)c wherec=logt+1s
hence number of IDs is ≤ (t + 1)p(n)+1+c .
count ID’s on a separate tape in base t +1 and p(n)+c +1 tape cells.
have two-tape machine M′ counting up to max IDs on extra tape
halt if counter exceeds maximal value (M accepts if no IDs are repeated)
converting to a single-tape machines gives polynomial blowup, hence exptime overall.
Savitch’s Theorem: PSPACE=NPSPACE
Theorem 10.5
PSPACE=NPSPACE
Let M be nondeterministic and polyspace bounded by p(n)
M has cp(n) different IDs.
DecideP(I,J,K)=I ⊢∗ J forIDsI andJ in≤K steps
This gives w ∈ L(M) iff I ⊢∗ J for initial ID I and accepting ID J in at most cp(n) steps
The bound on steps is valid, as M accepts iff M accepts without repeating IDs Remains. Implement P(I,J,K) taking polynomial space.
Recursive Doubling
Goal. Implement P(I,J,N) = I ⊢≤m J in deterministic polyspace
P(I, J, m): for all IDs K with length <= p(n) do {
if P(I, K, m/2) and P(K, J, m/2) then return true
return false
Q. How much space does this implementation need?
Recursive Doubling
P(I, J, m): for all IDs K with length <= p(n) do {
if P(I, K, m/2) and P(K, J, m/2) then return true
return false
Recursive Doubling
m = cp(n), so log cp(n) = p(n) recursive calls till base case
calls with argument m only induce one call with argument m/2 only need to remember current ID for function return
O(p2(n)) space in total
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com