CS 5315, Test 2, Tuesday, April 27, 2010

Name

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

1. A square-checker is a function that, given a program that always halts, checks whether this program always correctly compute n2. Prove that square-checkers are impossible.

2. Define what is NP, what is NP-hard, and what is NP-complete; no need to give a detailed definition of reduction.

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

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

8. Estimate Kolmogorov complexity of a string 04270427 ... 0427 (repeated 2010 times)

9. Describe, step by step, how to compute the product of 8 numbers in parallel. How many processors do you need? How many moments of time do you need?

10. Does the problem of computing the product of n numbers belong to the class NC? Explain your answer. What will the computation time for this problem be if we take communication time into consideration?

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 1%?

12. For a function (x1)2 + (x2)2 - 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. Find what is Π3PΣ2P.

14. Which class of the polynomial hierarchy corresponds to winning in 2 moves (i.e., to find a move such that whatever the opponent replies, you win).

15. Describe two possible schemes for solving NP-hard problems in polynomial time.