CS 535 Fall 2010 Assignment #3 Date Due: Wednesday, October 13 (or Thursday in class at the latest) Reading: Reread chapter 3, pages 42-46, Chapter 7, pages 145-151. Problems : 1. Let f: N --> N be a function computable in TIME(n^{4}) and let g: N --> N be a function computable in TIME(n^{3}).For f this means that there is a TM T which when started with some natural number x on its input tape halts within |x|

^{4}steps in the accepting state and with the number f(x) on a designated work tape.(i) Show that f(g(x)) (that is, f composed with g) can be computed in time (n

^{12}).2. (i). Prove that TIME (n

^{3}) is closed under difference. That is, if A and B are 2 languages in TIME (n^{3}) then so is A-B.(ii). It is easy to prove that TIME (n

^{2}) is closed under complement. (That is if L is in TIME (n^{2}) then so is the complement of L.)But it is not known if NTIME(n

^{2}) is also closed under complement. What goes wrong with the usual "reverse accepting and rejecting states" proof that TIME (n^{2}) is closed under complement when you try to do the same for NTIME(n^{2}).3. Page 129, Homework 6.3, parts 4 and 5.

4. Page 142, Problem 6.15 For this problem you can assume CLIQUE, as defined on page 141, is NP-complete.

5. Page 142, Problem 6.16

6. Page 142, Problem 6.17 For this problem you can assume the SAT problem is NP-complete.

7. Page 143, Problem 6.20 For this problem you can assume the SAT problem is NP-complete.

8. On page 7 of our book Example 1.7 discusses disjunctive normal form (DNF) and mentions the fact that for any Boolean formula there is an equivalent formula in DNF form.

Here is a proof that uses the fact above and proves that SAT is in P:

Given a Boolean formula F, convert it to DNF formula F'. [Note that a conjunction of variables and variable negations is satisfiable so long as there is no variable x which appears together with its negation in that conjunction. ]

Now go through the disjuncts of F' (each one is a conjunction) and see if there is some disjunct which does not contain some variable and its negation. If there is then accept F as being satisfiable. If not, reject. (END OF PROOF)

-------------------------------------------------

The problem you need to answer is: What is wrong with this proof ?