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 Higher Grades Now

Tutors Online