CS代写 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
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