CS 5315, Final Exam, Spring 2009


(Please do not forget to put your name on all extra sheets of paper)

1. Prove, from scratch, that the relation a > b is primitive recursive. The notion of a primitive recursion is a formalization of the for-loop. Translate your description of a > b into a program that uses for-loop(s) to compute a - b. Prove that this function is mu-recursive.

2. Prove that the function which is equal to n - 1 for n > 0 and undefined for n = 0 is mu-recursive. The notion of a primitive recursion is a formalization of the while-loop. Translate your description of this function into a program that uses while-loops.

3. Describe a Turing machine that computes n - 1. Use your Turing machine to design a new Turing machine for computing n - 2.

4. Is every computable function primitive recursive? mu-recurisve? Turing computable? Explain your answers (no need to produce detailed proofs).

5. What is a recursively enumerable (r.e.) set? Is the intersection of two r.e. sets always r.e.? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample.

6. Is it possible, given a program that always halts, to check whether this program correctly computes the function n - 1? If yes, explain how; if no, prove that such a procedure is not possible.

7. Define what is P, what is NP, what is NP-hard, and what is NP-complete. Give examples of NP-hard problems. Hint: no need to give an exact definition of reduction.

8. Estimate Kolmogorov complexity of a string 512512 ... 512 (repeated 1,000 times).

9. Use the general algorithm for transforming propositional expressions into DNF and CNF forms to transform a Boolean expression (x1 - 0.7) * (x2 + 0.3) > 0.3 into DNF and CNF forms. Explain where this transformation is used in the proof that computational satisfiability is NP-hard.

10-13. Reduce the satisfiability problem for the formula (x1 \/ x3) & (x1 \/ x2 \/ -x3) to:

14. Prove that the 4-coloring problem is NP-hard. You can use the fact that 3-coloring is NP-hard.

15-16. Describe how to compute the sum of two n by n matrices in parallel.

17. Explain which class of the polynomial hierarchy contains three-move game problems.

18. Describe a possible physical scheme that would enable us to solve NP-hard problems in polynomial time.