Theory of Computations,
Final Exam for the course
CS 5315, Spring 2016

Name: _____________________________________________________

You can use up to 5 handwritten pages of notes. Feel free to use extra sheets of paper if needed, but if you do, do not forget to put your name on each of these sheets.

1. Primitive recursive and mu-recursive functions:

1a. Why do we need to study primitive-recursive and mu-recursive functions in the first place? What programming concepts do they correspond to?

1b. Translate, step-by-step, the following double loop into a mu-recursive expression:

 int s = 2;
 while(s < a){
   for(int i = 1; i <= b; i++)
     {s = s * s;}
You can use the multiplication function is this description. What is the result of this program when
a = b = 3?

1c. Prove, from scratch, that the function a/b is primitive recursive. Provide a simpler proof that this function is mu-recursive.

1d. Is Kolmorogov complexity primitive recursive? mu-recursive? Explain your answers.

2. Computable sets, computable functions, and Turing machines:

2a. Why do we need to study decidable and recursively enumerable (r.e.) sets?

2b. Is the complement to a r.e. set always r.e.? If yes, prove it, if no, provide a counterexample.

2c. Prove that it is not possible, given a program that always halts, to check whether this program always computes n + 1.

2d. Design a Turing machine that computes n + 1 in binary code. Trace this machine on the example of n = 112.

3. NP-hardness:

3a-d. Reduce the satisfiability problem for the formula (a \/ ~b) & (~a \/ b) & (a \/ b \/ c) to:

    a) 3-coloring,
    b) clique,
    c) subset sum problem, and
    d) interval computations.

3e. In proofs of what results are these reductions used? What do we gain by proving that a problem is NP-hard?

3f. Use the definitions of the classes P, NP, NP-hard, and NP-complete to describe, for each of these four classes, whether this class contains 3-coloring, 2-SAT, and interval computations. Explain your answers.

3g. Give two examples of why the current definition of a feasible algorithm is not perfect:

  • an example when an algorithm is feasible according to this definition but not practically feasible, and
  • an example when an algorithm is not feasible according to this definition but is practically feasible.

4. Parallelization:

4a. Does matrix multiplication problem belong to the class NC? Explain your answer.

4b. If we parallelize and take into account communication time, what is the fastest that we can compute the product of two matrices? Explain your answer.

4c. Where are similar arguments used in the proof that satisfiability is NP-hard?

4d. What are the physical assumptions behind these arguments? Give two examples of how non-standard physics -- in which these assumptions are not satisfied -- can be used to solve NP-hard problems in polynomial time.

5. How to solve NP-hard problems?

5a. Suppose that a probabilistic algorithm for checking the program correctness misses the program's mistake 10% of the time. How many times do we need to repeat this algorithm to achieve reliability of 99.99%? And why do we need probabilistic algorithms in the first place?

5b. Apply both greedy algorithms to solve the following particular case of the knapsack problem: we have 4 objects with weights 2, 3, 4, and 5, values 10, 12, 12, and 15, and the overall weight of 5. Why do we need to use these algorithms, if they do not produce optimal results?

5c. (For extra credit) Give an example of how quantum computing can speed up computations.

6. Beyond NP: polynomial hierarchy:

6a. Which class of the polynomial hierarchy contains optimization problems? The problem of winning in 2 moves? Explain your answers.

6b. Which class of polynomial hierarchy contains Σ2Π3?

6c. Give an example of an oracle A for which PA = NPA. Explain your answer.

7. Projects:

7a. Briefly describe your project for this class.

7b. Briefly describe someone else's project for this class.