1.
Prove each of the
following. You may use any of the theorems stated in the lecture notes and
homework assignments.
a.
If A ∈ PSPACE-Complete, B ∈ PSPACE, and A ≤p B, then B ∈ PSPACE-Complete.
b.
If there exists A ∈ PSPACE − NP, then for all L ∈ PSPACE-Complete, L ∉ NP.
c.
For any A, B ∈ PSPACE-Complete, A ≤p B and B ≤p A.
d.
Co-NP ⊆ PSPACE. (Co-NP is defined in this note.)
2.
Let
ψ(x1,
x2, x3) = (¬x1 ∨ x2 ∨ ¬x3) ∧ (x1 ∨ ¬x2 ∨ x3)
a.
Give an evaluation tree
for ψ by assigning xi = 0 and 1, 1 ≤ i ≤ 3. You may terminate a
branch as soon as its value is known.
b.
For each of the
following formulas, decide if it is true or false and which player (E or A) has
a winning strategy. Justify your answers based on the evaluation tree built in
(a).
i.
∃x1∀x2∃x3ψ(x1, x2, x3)
ii.
∀x1∃x2∀x3ψ(x1, x2, x3)
iii.
∃x1∀x2∀x3ψ(x1, x2, x3)
3.
Consider QBFs:
Q1x1Q2x2 ···
Qkxk ψ(x1, …, xk)
a.
There is a type of ψ(x1,
…, xk) such that, regardless of what quantifiers Q1, Q2,
…, Qk are, player E always wins no matter what values it and
player A select in their turns. What type of formula is it? Justify your
answer.
b.
There is a type of ψ(x1,
…, xk) such that, regardless of what quantifiers Q1, Q2,
…, Qk are, player A always wins no matter what values it and
player E select in their turns. What type of formula is it? Justify your
answer.
Get Free Quote!
410 Experts Online