Computer Science > STUDY GUIDE > University of Waterloo - CS 21soln-final (All)

University of Waterloo - CS 21soln-final

Document Content and Description Below

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 v... ia 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]

Last updated: 2 years ago

Preview 1 out of 5 pages

Buy Now

Instant download

We Accept: