Name

1. Describe the function f = PR(0, σ(π³₁) + π³₂) 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₁₀ = 1000₂ 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²) 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 Σ₂P^Π₂P.

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.