Reference no: EM132693790

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.