CS 21 Decidability and Tractability Winter 2014
Final Exam Solutions
Posted: March 19
If you have not turned in the final, obviously you should not consult these solutions.
1. (a) L is in PSPACE via the following rec
...
CS 21 Decidability and Tractability Winter 2014
Final Exam Solutions
Posted: March 19
If you have not turned in the final, obviously you should not consult these solutions.
1. (a) L is in PSPACE via the following recursive algorithm. In general we are given
G, k, (Si, Ti), . . . (Sn, Tn)
and the question is whether player 1 can win (if i is odd) and whether player 2 can defeat
player 1 (if i is even).
We produce G′ by deleting Si and G′′ by deleting Ti. If i is odd we want to know if
player 1 can win so we recursively check whether player 2 can defeat player 1 given each
of the following 2 inputs:
G′, k, (Si+1, Ti+1), . . . (Sn, Tn)
and
G′′, k, (Si+1, Ti+1), . . . (Sn, Tn).
If yes to both, then player 1 can’t win and we return ”no”. Otherwise we return ”yes”. If
i is even we want to know if player 2 can defeat player 1 so we recursively check whether
player 1 can win given each of the following 2 inputs:
G′, k, (Si+1, Ti+1), . . . (Sn, Tn)
and
G′′, k, (Si+1, Ti+1), . . . (Sn, Tn).
If yes to both, then player 1 can win no matter what player 2 does so we return ”no”;
otherwise we return ”yes”.
The base case is checking whether a graph has a clique of size at least k, which is in NP
and hence in PSPACE. The overall recursive algorithm thus has polynomial recursion
depth and uses polynomial space at each level, so it is runs using only polynomial space.
(b) We reduce from QSAT, as suggested. We have a triple of nodes for each of the m clauses,
labeled with the literals in that clause. We add all edges between different triples (but
none between nodes of a given triple).
[Show More]