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.

 


Related Questions in computer science category