## Theory of Computations, Homeworks for the course CS 5315, Spring 2011

1. (Due January 26) Provide a detailed proof (as we did in class) that the bounded subtraction a -- b is primitive recursive.

2. (Due January 26) Prove that the function a -- 2 is primitive recursive.

3. (Due January 26) Prove that the function n3 + 5 * n is primitive recursive.

4. (Due February 8) Report on your work on your class project.

5. (Due February 14) Write down, in detail, the proof that not every computable function is primitive recursive -- the same proof that we had in class.

6. (Due February 16) Prove that the integer division function / is mu-recursive.

7. (Due February 21) It is known that the Ackermann function is not primitive recursive. Let us call a function Ackermann-primitive recursive if it can be obtained from 0, sigma, projections, and the Ackermann function by using composition and primitive recursion. Prove that not every computable function is Ackermann-primitive recursive.

8. (Due February 21) If A is r.e. and B is decidable, is their intersection r.e.? decidable?

9. (Due February 23) Design a Turing machine that computes a 0 function in binary code.

10. (Due February 23) Design a Turing machine that computes the function n + 1 in binary code.

11. (Due February 23) Design a Turing machine that computes π31.

12. (Due February 28) Design a Turing machine that computes π32.

13. (Due March 2) Reproduce, in detail, the proof that we had in class: that zero-checker is not possible.

14. (Due March 2) Prove a relativized version of the halting problem: that for every oracle h, if we consider programs that use this oracle ("h-program"), then no h-algorithm is possible that, given an h-program p and data d, checks whether p halts on d.

15. (Due March 2) For extra credit: Relativize the zero-checker result: prove that for every oracle h, there is no h-algorithm that, given an h-program f(n) that always halts, checks whether f(n) always returns 0.

16. (Due March 30) Similarly to what we did in class, trace the reduction of the following problem to propositional satisfiability: given a bit x, find a bit y for which x implies y.

17. (Due April 4) Show the reduction of propositional satisfiability problem SAT for CNF formulas to the 3-SAT problem (propositional satisfiability for 3-CNF formulas) on the example of the following formula: (x1 \/ x2 \/ x3 \/ x4) & (~x1 \/ ~x2 \/ ~x3 \/ ~x4).

18. (Due April 4) Show the reduction of SAT to Clique problem on the example of the following formula: (x1 \/ x2) & (~x1 \/ ~x2) & (x3 \/ x4).

19. (Due April 4) Show the reduction of SAT to the 3-coloring problem on the example of the following formula: (x1 \/ x2) & (~x1 \/ ~x2) & (x3 \/ x4).

20. (Due April 4, for extra credit) Prove that 4-coloring (i.e., the problem of coloring a graph in 4 colors) is NP-hard.

21. (Due April 4) Show the reduction of 3-SAT to exact change problem on the example of the following formula: (x1 \/ x2) & (~x1 \/ ~x2) & (x3 \/ x4).

22. (Due April 6) On an example, show how a propositional satisfiability problem can be reduced to interval computations.

23. (Due April 6) Let us assume that we have a random-numbers-using test for which,

• if the test result fails, this means the original method is wrong, but
• if the original method is wrong, then the test will pass with a probability p0= 1/4.
How many times do we need to run this test to reduce a probability of releasing the wrong program to pdesired = 10-4?

24. (Due April 6) On an example of a propositional satisfiability problem in CNF form, show step-by-step how a greedy algorithm that we discussed in class will work.

25. (Due April 11) On an example of an Ali-Baba (knapsack) problem, show step-by-step how two how greedy algorithms that we discussed in class will work.

26. (Due April 11) What is Π2P Σ3P?