Prove each of the following. You may use any of the theorems stated in the lecture notes and homework assignments.
computer science
Description
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.
