**Name**

(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:

- 3-coloring
- clique
- subset sum problem
- interval computations

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.

- Does this problem belong to the class NC? explain your answer.
- Is NC a subset of P? explain your answer.
- Is NC equal to P? Explain the relationship between this equation and linear programming problems. Give an example of a linear programming problem.
- What will be the computation time if we take communication time into consideration? Where is a related argument used in the proof that satisfiability is NP-hard?

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