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(n4)
and let g: N --> N be a function computable in TIME(n3).

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 (n12).


2. (i). Prove that TIME (n3) is closed under difference.
That is, if A and B are 2 languages in TIME (n3) then so is A-B.



(ii). It is easy to prove  that  TIME (n2) is closed 
under complement. (That is if L is in TIME (n2) then so is the complement of L.)


But it is not known if NTIME(n2) is also closed under complement.

What goes wrong with the usual "reverse accepting and rejecting states" proof
that TIME (n2) is closed under complement when you try to do the same
for NTIME(n2).



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 ?