## Theory of Computation, Homeworks for the course CS 5315, Spring 2012

1. (Due January 25) Prove that an is primitive recursive.

2. (Due January 25) Prove that n! is primitive recursive.

3. (Due January 25) Prove that n2 + 3 is primitive recursive.

4. (Due January 25) Prove that the implication a --> b is primitive recursive.

5. (Due January 30) Write down the proof that not every computable function is primitive recursive.

6. (Due February 1) Prove that division a/b is mu-recursive.

7. (Due February 1) Propose a topic for a class project.

8. (Due February 6) A function is called Ackermann-primitive recursive if it can be obtained from 0, σ, πki, and the Ackermann function A(n) by using composition and primitive recursion. Prove that there exist a computable function which is not Ackermann-primitive recursive.

9. (Due February 6) Prove that the following function f(n) is mu-recursive: it is equal to 3 when n = 5, it is equal to 5 when n = 3, and it is undefined for all other n.

10. (Due February 8) Design a Turing machine that adds two given numbers.

11. (Due February 8) Design a Turing machine that computes the previous number.

12. (Due February 8) Design a Turing machine that computes π31.

13. (Due February 8) Design a Turing machine that computes π32.

14. (Due February 13) Use the algorithm that we described in class to design a Turing machine that computes a composition f(g(n)) of the functions f(n) = n + 1 and g(n) = prev(n) (i.e., n - 1 if n > 0 and 0 otherwise). Trace this new Turing machine step-by-step for n = 0.

15. (Due February 13) Use the algorithm that we described in class to design a Turing machine that computes a composition f(g(n)) of the functions f(n) = prev(n) (i.e., n - 1 if n > 0 and 0 otherwise) and g(n) = n + 1. Trace this new Turing machine step-by-step for n = 1.

16. (Due February 15) Design a Turing machine for adding 1 in binary code, and test it on an example. Ignore the possibility of an overflow.

17. (Due February 15, for extra credit) Use the general idea of implementing mu-recursion to design a Turing machine that computes μn.P(n), where P(n) = n when n = 0 or n = 1, and P(n) = 0 for all other n.

18. (Due February 20) Reproduce the proof that we had in class, that there is no algorithm for checking whether a given program halts on given data.

19. (Due February 22) Reproduce the proof that we had in class, that there is no algorithm that, when applied to a function which is known to always halt, would check whether this function always produces 0.

20. (Due February 27) Prove that a 2n-checker is impossible.

21. (Due February 27) Try your best to solve problems from last year's Test 1 which was distributed in class.

22. (Due March 28) Illustrate the proof that satisfiability is NP-hard on the example the following simple NP-problem: given a bit x, find a bit y for which x --> y. The description should be similar to what we had in class, where the requirement for the bit y was different: we wanted to find a bit y for which x = y.

23. (Due March 28) Show how the following propositional satisfiability problem can be reduced to graph coloring: (x1 \/ -x2 \/ -x3) & (-x1 \/ x2 \/ x3); here, -a means negation.

24. (Due April 2) Show, on the example of the propositional formula (x1 \/ -x2 \/ x3) & (-x1 \/ x2) & (-x2 \/ x3), how the propositional satisfiability problem can be reduced to the clique problem.

25. (Due April 2) Show, on the example of the propositional formula (x1 \/ -x2 \/ x3) & (-x1 \/ x2) & (-x2 \/ x3), how the propositional satisfiability problem can be reduced to the subset sum problem.

26. (Due April 2) Prove that 5-coloring problem -- the problem of coloring a graph in 5 colors -- is NP-hard.

27. (Due April 2) Show, on the example of the propositional formula (x1 \/ -x2 \/ x3) & (-x1 \/ x2) & (-x2 \/ x3), how the propositional satisfiability problem can be reduced to the main problem of interval computations.

28. (Due April 4) Take any propositional formula, and show how we can find a satisfying vector for this formula by checking propositional satisfiability of this and related formulas.

29. (Due April 4) Take any instance of the subset sum problem, and show how we can find a solution to this problem by checking the existence of solution to this and related instances.

30. (Due April 4) Find the classes of the polynomial hierarchy corresponding to Π2PΠ3P and Π2PΣ3P.

31. (Due April 9) Show how best to compute the product of eight numbers in parallel (if we have a potentially unlimited number of processors): how many processors we need, and how much time will this computation take.

32. (Due April 9) Show how best to compute the maximum of eight numbers in parallel (if we have a potentially unlimited number of processors): how many processors we need, and how much time will this computation take.

33. (Due April 11) Suppose that for a probabilistic algorithms, the probability of a wrong answer is 1/2. How many times do we need to repeat this algorithm to make sure that the probability of a wrong answer does not exceed 10-4?

34. (Due April 16) Come up with an instance of the Ali Baba problem, and show how both greedy algorithms that we learned in class -- selecting the most expensive object and selecting the object with the largest value per unit weight -- will solve this problem.

35. (Due April 16) On an example of a propositional formula, show how a greedy algorithm that we learned in class will find a satisfying for this formula.