CS 5315, Final Exam, Spring 2010

Name

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

1. Prove, from scratch, that the relation a = b is primitive recursive. Primitive recursion is a formalization of the for-loop. Translate your description of a = b into a program that uses for-loop(s) to compute a = b. Prove that this function is mu-recursive.

2. Prove that the function which is equal to 1 for a = b and undefined for all other a and b is mu-recursive. The notion of a mu-recursion is a formalization of the while-loop. Translate your description of this function into a program that uses while-loops.

3. Describe a Turing machine that computes the function a = b, i.e., that uses an input (a, b) and returns 1 ("true") when a = b and 0 ("false") when a is different from b. Feel free to design a Turing machine with two heads. For example, you can move both heads to the start of the words a and b, and then move both heads one step at a time. If they both encounter a blank space at the same time, this means that a = b, otherwise a =/= b.

4. Is every computable function primitive recursive? mu-recursive? Turing computable? Explain your answers (no need to produce detailed proofs, just explain the main ideas).

5. What is a recursively enumerable (r.e.) set? What is a decidable set? Is the intersection of a r.e. set and a decidable set always r.e.? always decidable? For each of these questions, if your answer is "yes", provide a proof; f your answer is "no", provide a counterexample.

6. Is it possible, given a program that always halts, to check whether this program correctly computes the function a = b? If yes, explain how; if no, prove that such a procedure is not possible.

7. Define what is NP, what is NP-hard, and what is NP-complete; give the main idea of what is reduction.

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

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

9. What is Kolmogorov complexity? Where is this notion used? Estimate Kolmogorov complexity of a string 05120512 ... 0512 (repeated 2010 times).

10. Describe, step by step, how to multiply two 2 x 2 matrices in parallel. How many processors do you need? How many moments of time do you need? Does the problem of computing the product of two n x n matrices belong to the class NC? Explain your answer. What will the computation time for this problem be if we take communication time into consideration? Where is a related argument used in the proof that satisfiability is NP-hard?

11. 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.1%? Give an example of a probabilistic algorithm.

12. For a function (x1)2 + 2 * (x2)2 - x1 * x2, find its exact range for x1 from [0,1] and x2 from [-1,1] by using calculus, and then compute the enclosure by using naive interval computations.

13. Which class of the polynomial hierarchy corresponds to optimization? Explain your answer.

14. Describe at least two possible physical schemes that has a potential of enabling us to solve NP-hard problems in polynomial time.

15. Briefly describe what you did as part of your project for the class.

16. Describe one of the projects that other students presented in class.