程序代写 COMP3630/6360: Theory of Computation Semester 1, 2022

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