CS6505: Computability & Algorithms Homework 4. Due in c

CS6505: Computability & Algorithms Homework 4. Due in class on Wed Feb 15. 1. Given a graph G a matching in G is a set of edges such that no two of them share a vertex. Let MATCHING = f(G; k) : G has a matching of size kg i.e. the language consisting of graphs G with matchings of size at least k. Show that this language is in NP. 2. Let PRIMES= fn 2 N : n is a prime numberg. Show that PRIMES is in co-NP. 3. A graph G is said to be bipartite if the vertices can be divided into two parts such that every edge of G goes between the two parts and there are no edges within either part. Dene the language: BIPARTITE = fG : G is bipartite g. Show that this language is in NP co-NP. 4. (a) Show that a given boolean formula F can be converted to an equivalent alternating CNF formula of size poly(jFj) i.e. to a formula of the form Q1x1Q2x2:::Qkxk F0 where each Qi is a quantier either 9 or 8 the quantiers alternate and F0 is a CNF formula. (b) Deduce that TQBF is PSPACE-complete when restricted to alternating CNF formulas. (c) (Bonus) Consider the following game played between two players A and B on a directed graph G: player A starts and chooses a vertex v in G. Player B can then choose any vertex connected to v. The players alternately choose vertices that form a path in G without choosing any vertex twice. The player who cannot move loses. Dene the language L = f(G; s) : player A has a winning strategy starting from vertex sg. Show that L is PSPACE-complete. (Hint: Use part (ii) for a reduction). 1
Attachments: