Final Exam for the course

CS 5315, Spring 2013

Name: _____________________________________________________

1. Describe the function f = σ(PR(0,
π^{3}_{1} + π^{3}_{2}))
in normal terms. For this function f, what is the value f(6,
3)?

2. Prove, from scratch, that the remainder function % is primitive recursive and μ-recursive. Start with the definitions of a primitive recursive function and a μ-recursive function, and use only this definition in your proof -- do not use results that we proved in class.

3. Prove that not every μ-recursive function is primitive recursive.

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

5. Prove that the union of two recursively enumerable sets A and B is recursively enumerable. Based on your proof, answer the following question: if a number 6 was generated by the algorithm corresponding to the second set at moment 3, when will this number be printed by an algorithm corresponding to the union?

6. To prove that the the union of two recursively enumerable
sets A and B is recursively enumerable, a student proposed the
following alternative algorithm: "First, we produce all the
elements of A; then, we produce all the elements of B". Give an
example when this algorithm will not work. *Hint:* sets
can be infinite.

7. Prove that the halting set is recursively enumerable. If a program p = 1 halts on data d = 2 at moment t = 3, at what moment of time will the pair (p, d) printed by the corresponding algorithm?

8. Prove that the union of a decidable set and a recursively enumerable set is always recursively enumerable. Is such a union always decidable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

9. Prove that it is not possible, given a program that always
halts, to check whether this program always computes
n^{4}.

10. Design a Turing machine that computes a function f(n) = 2
* n in binary code (the number n is written starting with
its highest bit; e.g., 6_{10} = 110_{2} is
written as # 1 1 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 * n.

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 three classes contain the problem of
computing the component-wise sum of two arrays (see Problem
14)? Ali-Baba problem? (*Reminder*: we have a list of
objects with known prices p_{i} and weights
w_{i}; we need to select some of these objects so that
the total price is at least P and the total weight does not
exceed W.)

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

- 3-coloring;
- 5-coloring;
- clique;
- Ali Baba problem (see Problem 11);
- interval computations.

14. Consider the problem of computing the component-wise sum c
= (c_{1}, ..., c_{n}) of two vectors a =
(a_{1}, ..., a_{n}) and b = (b_{1},
..., b_{n}), where c_{i} = a_{i} +
b_{i}

- Does this problem belong to the class NC? Explain your answer.
- Is NC 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 how using non-Euclidean physics can potentially lead to faster computations -- such as solving NP-hard problems in polynomial time.

15. 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%?

16. Find what is
Σ_{2}P^{Π4P}.

17. Which class of the polynomial hierarchy corresponds to finding the value x at which a given objective function f(x) attains the smallest possible value?

18. What is the Kolmogorov complexity of a sequence 011011 ... 011 (repeated 2,013 times)?

19-20. Describe your project for the class. Describe someone else's project for the class.