1. 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 dot product (a, b) = a1 * b1 + ... + an * bn of two vectors a = (a1, ..., an) and b = (b1, ..., bn) of size n? the main problem of interval computations?
2-6. Reduce the satisfiability problem for the formula (~x1 \/ x2) & (~x1 \/ ~x2) & (~x1 \/ ~x2 \/ x3) to:
7-9. A straightforward algorithm takes time O(n) to compute the dot product of two vectors of size n.
10. If a probabilistic algorithm produces a result with the probability of error 1/4, how many times do we need to repeat it to reduce the probability of error to 0.1%?
11. Find what is Π2PΣ4P.
12. Which class of the polynomial hierarchy corresponds to winning in three moves?
13. What is the Kolmogorov complexity of a sequence 100100 ... 100 (repeated 2,014 times)?