Computational Complexity, III

1. (*) Construct a p-reduction of CLIQUE to SAT. (Hint: consider boolean variables representing the adjacency matrix of a graph together with additional n · k variables v_{ij}, where n is the size of the graph and k is the size of the clique. Variable v_{ij} will be true iff i-th element of a clique is j-th vertex of a graph.)

2. (Huiswerk) Consider the following variant of CLIQUE problem: determine, if a given graph of size n has a clique of size [n/2]. Show that this problem is NP -complete.

3. Find good upper bounds on the space complexity of SAT and CLIQUE.

4. For any TM M such that n = o(Space_{M}(n)) there is a TM N that decides the same language and Space_{N}(n) ≤ 1/5 Space_{M}(n) for all but finitely many n. (Hint: use a suitably larger tape alphabet.)

5. Determine which of the following quantified boolean formulas is valid: ∃pp, ∀pp, ∃p∀q(p → q), ∀p((p → q) → (¬q → ¬p)).

6. Determine, if the following is a correct rule of inference in quantified boolean logic: If ϕ → ψ is valid (under all free variable assignments), then ϕ → ∀pψ is valid. Under what condition it is?

7. Joost has proved a remarkable theorem: every language in PSPACE can actually be recognized in linear space. His proof goes as follows: It is easy to see that the validity of quantified boolean formulas (TQBF) can be recognized in linear space. Since TQBF is PSPACE-complete, any language L ∈PSPACE is p-reducible to it. Hence, recognizing L also takes linear space. Joost is, of course, wrong. Find a flaw in his reasoning.