**Name**

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

1. Describe the function f = PR(0,
σ(π^{3}_{1}) + π^{3}_{2})
in normal terms. For this function f, what is the value f(6,
3)?

2. Prove, from scratch, that the function a ≤ b is primitive recursive and μ-recursive. Start with the definitions of a primitive recursive and a μ-recursive functions, and use only these definitions in your proof -- do not use results that we proved in class as given, you must prove everything.

3. Is every primitive recursive function μ-recursive? Is every everywhere defined μ-recursive function primitive recursive? For each of these questions:

- if your answer is yes, prove it,
- if your answer is no, give a counterexample and explain why this is a counterexample.

4. Design a μ-recursive function f(a, b) that represent "nand" limited to truth values: f(1, 0) = f(0, 1) = f(0, 0) = 1, f(1, 1) = 0, and f(a, b) is undefined for all other pairs (a, b).

5. Is the difference A − B between two decidable sets decidable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

6. Is the difference between two recursively enumerable sets recursively enumerable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

7-8. Design a Turing machine that computes a function f(n) = 4
* n in binary code. Assume that the number n is given
starting from the largest bit: for example, 8_{10} =
1000_{2} is given as # 1 0 0 0 # # # # ... The
algorithm for multiplying by 4 is simple: we add 00 at the end.
For example, for the above 8, we get # 1 0 0 0 0 0 # # # # ...
Use the general algorithm for generating a Turing machine for
the composition to design a Turing machine that computes the
function f(f(n)) = 4 * f(n) = 4 * (4 * n) = 16 * n.

9. A student produced a program, proved that this program always halts, and claims that this program always computes 4 * n. Is there a general way of checking whether this program always computes 4 * n? If yes, explain how, if no, prove that this is not possible.

10. What is the Kolmogorov complexity of a sequence 100100 ... 100 (repeated 2,014 times)?

11. Define what is P, what is NP, what is NP-hard, and what is NP-complete; no need to give a detailed definition of reduction. Which of these four classes contain the problem of subtracting two matrices? the clique problem?

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

- 3-coloring;
- 5-coloring;
- clique;
- subset sum problem;
- interval computations.

14-15. A straightforward sequential algorithm takes time
O(n^{2}) to compute the sum of two matrices.

- How fast can we solve this problem in parallel -- if we ignore the communication time? Explain how exactly, and how many processors we need for such fast computations.
- Does this problem belong to the class NC? Explain your answer.
- Is NC equal a subset of P? equal to P? explain your answer.
- If we parallelize and take into account communication time, what is the fastest that we get with such parallel algorithms? Explain your answer.
- Where are similar arguments used in the proof that satisfiability is NP-hard?
- Explain what is the physics behind these arguments and describe at least two different schemes for using non-standard physics can potentially lead to faster computations -- such as solving NP-hard problems in polynomial time.

16. If a probabilistic algorithm produces a result with the probability of error 1/2, how many times do we need to repeat it to reduce the probability of error to 0.5%?

17. Find what is
Σ_{2}P^{Π2P}.

18. Which class of the polynomial hierarchy corresponds to minimization?

19. Briefly describe your project for this class.

20. Briefly describe someone else's project for this class.