## 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.