Theory of Computations, Final Exam for the courseCS 5315, Spring 2011

1-2. Prove, from scratch, that the binary remainder function a % 2 (or, in mathematical notations, a mod 2) is primitive recursive. Start with the definition of a primitive recursive function, and use only this definition in your proof -- do not use results that we proved in class. Prove also that this function is μ-recursive.

3. Design a Turing machine that, given a binary number a, computes the remainder f(a) = a % 2. For example, for a binary number 11012 (which is equivalent to 13), this Turing machine should return 1. Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(f(a)).

4-5. A student produced a program that claim to provide a new way of computing a % 2. Is there a general way to check that this program halts? If yes, explain how, if no, prove that this is not possible. Suppose now that for this particular proram, we have proven that it always halts. Is there a general way of checking whether this program always produced the correct result? If yes, explain how, if no, prove that this is not possible.

6. Is the intersection of two recursively enumerable (r.e.) sets always r.e.? If yes, prove; if no, provide a counter-example and prove that this counter-example is not r.e.

7-8. 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. For each of these four classes, indicate whether this class contain the clique problem and whether this class contains a problem of computing the remainder a % 2.

9-13. 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.

14-17. A straightforward algorithm for adding two matrices takes time O(n^2) to compute the sum of two square matrices of size n x n.

• If we do not take into account communication time, how fast can we solve this problem? Is this problem in the class NC?
• 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 how using non-Euclidean physics can potentially lead to faster computations -- such as solving NP-hard problems in polynomial time.

18-19. What is the Kolmogorov complexity of a sequence 101101 ... 101 (repeated 100,000 times)? Prove that Kolmogorov complexity is not computable. For extra credit: Explain Gell-Mann's potential physical scheme for using equations explicitly depending on Kolmogorov complexity for computing hard problems.

20. Which class of the polynomial hierarchy corresponds to winning a game in two moves? Explain your answer