CS 5315, Final Exam, Wednesday, May 9, 2012

Name

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

1. 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.

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

• if your answer is no, give a counterexample and explain why this is a counterexample.

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

4. Is the intersection of two decidable sets decidable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

5. Is the intersection of two recursively enumerable sets recursively enumerable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

6-7. Design a Turing machine that computes a function f(n) = n + 1 in binary code. Assume that the number n is given starting from the smallest bit: for example, 810 = 10002 is given as # 0 0 0 1 # # # # ... The algorithm for adding 1 is simple: we replace all 1s by 0s until we meet the first 0 or blank space, after which we replace it with 1 and stop (do not forget to rewind the Turing machine). For example, for the above 8, there are no 1s after the initial blank, so we replace the first 0 by 1 and stop. For 1110 = 10112, which is represented as # 1 1 0 1, we should get # 0 0 1 1. Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(f(n)) = f(n) + 1 = (n + 1) + 1 = n + 2.

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

9. What is the Kolmogorov complexity of a sequence 01000100 ... 0100 (repeated 5,092,012 times)?

10. 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 multiplying all numbers in a given array? the interval computations problem?

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

• 3-coloring;
• clique;
• subset sum problem;
• interval computations.
Use a greedy algorithm to find a solution to the original satisfiability problem.

12-13. A straightforward algorithm takes time O(n) to compute the product of all the elements in an array of size n.

• How fast can we solve this problem -- 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.

14. 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 2%?

15. Find what is Π3PΠ2P.

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

17. Briefly describe your project for this class.

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