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:
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.