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 ?