CS 5315, Final Exam, Monday May 12, 2014

Name

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

1. Describe the function f = PR(0, σ(π31) + π32) 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, 810 = 10002 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(n2) 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 Σ2PΠ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.