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
PSPACE completeness Quantified Boolean Formulae QBF is PSPACE complete
Additional Reading: Chapter 11 of HMU.
PSPACE completeness
Definition 10.1
A problem L is PSPACE hard if there is a polytime reduction from any PSPACE problem to L.
A problem L is PSPACE complete, if it is PSPACE hard and in PSPACE. Q. Why polytime, and not polyspace reductions?
Observation.
Let L be a PSPACE complete problem.
1 If L ∈ P, then P = PSPACE.
2 if L ∈ NP, then NP = PSPACE.
Quantified Boolean Formulae
Definition 10.2
If V is a set of variables, then the set of quantified boolean formulae over V is given by: Everyvariablev∈V isaQBF,andsoarettandff
If φ,ψ are QBF, then so are φ∧ψ and φ∨ψ
If φ is a QBF, then so is ¬φ.
IfφisaQBFandv∈V isavariable,then∃vφand∀vψareQBF. Definition 10.3
In a QBF φ, an occurrence variable v is bound if it is in the scope of a quantifier ∀v or ∃v. The variable v is free otherwise.
If x ∈ {tt,ff} is a truth value, then φ[x/v] is the result of replacing all free occurrences of v with x.
Evaluation of QBFs
Observation.
A QBF φ without free variables can be evaluated to a truth value: eval(∀vφ) = φ[tt/x] ∧ φ[ff /x]
eval(∃vφ) = φ[tt/x] ∨ φ[ff /x]
and quantifier-free formulae without free variables can be evaluated.
QBFs versus boolean formulae.
abooleanformulaφinvariablesv1,…,vn issatisfiableif∃v1∃v2…∃vnφevaluates to true.
φ is a tautology if ∀v1∀v2 …∀vnφ evaluates to true. Definition 10.4
The QBF problem is the problem of determining whether a given quantified boolean formula without free variables evaluates to true:
QBF = {φ | φ a true QBF without free variables}
QBFs vs Boolean Formulae
evaluating a boolean formula without free variables is in P. (∀vφ) φ[tt/x] ∧ φ[ff /x]
(∃vφ) φ[tt/x] ∨ φ[ff /x]
the resulting formula may be exponentially large
but this shows that QBF is in EXPTIME. Q. Can we do better?
QBF is in PSPACE
Main Idea.
to evaluate ∀vφ, don’t write out φ[tt/v] ∧ φ[ff /v]. instead, evaluate φ[tt/v] and φ[ff /v] in sequence. avoids exponential space blowup
Algorithm evalqbf (phi) = case phi of
– tt: return tt
– phi /\ psi: if evalqbf(phi) then evalqbf(psi) else false
– forall v phi: if evalqbf(phi[tt/v]) then evalqbf (phi[ff/v]) else false
– (other cases analogous)
Given QBF φ of size n:
at most n recursive calls active
each call stores a partially evaluated QBF of size n total space requirement O(n2)
QBF is PSPACE-complete
Proof IdeaNote.
Let L be in PSPACE.
Then L is accepted by a polyspace bounded TM with bound p(n)
Ifw∈L,thenMacceptsin≤cp(n) moves
construct QBF φ: ‘there is a sequence of cp(n) ID’s that accepts w use recursive doubling to express this in polytime.
The Gory Detail
Variables.
Need O(p(n)) variables to represent ID:
yj,A = tt iff the j-th symbol of the ID is A, 1 ≤ j ≤ p(n) + 1 tuples.
Structure of the QBF.
φ = (∃I0)(∃If )S ∧N ∧F ∧U I0 and If are initial / accepting IDs
S says that I0 = q0w
F says that If is accepting
U says that every ID has at most one symbol per position
N says that there is a sequence of ID’s of length ≤ cp(n) from I0 to If . S, F, and U are as in Cook’s theorem.
Recursive Doubling
N = N(I0, If ): have sequence of length ≤ cp(n) from I9 to If .
Detour: N0(I,J) = I ⊢∗ J in ≤ 1 steps: as for Cook’s theorem Detour:Ni(I,J)=I⊢∗Jin≤2i steps:
Ni(I,J) = (∃K)(∀P)(∀Q)[(P,Q) = (I,K)∨(P,Q) = (K,J) → Ni−1(P,Q)]
Could also say (∃K)(Ni−1)(I,K) ∧ Ni−1(K,J))
this would write out Ni−1 twice, doubling formula size at each step above trick is key step in proof to keep formula size small
Let N(I0,If ) = Nk(I0,If ) where 2k ≥ cp(n) (note k ∈ O(p(n))
each Ni can be written in O(p(n)) many steps, plus the time to write Ni−1
so O(p(n)2) overall
By construction, φ = tt iff M accepts w.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com