Name

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) = a₁ * b₁ + ... + a_n * b_n of two vectors a = (a₁, ..., a_n) and b = (b₁, ..., b_n) of size n? the main problem of interval computations?

2-6. Reduce the satisfiability problem for the formula (~x₁ \/ x₂) & (~x₁ \/ ~x₂) & (~x₁ \/ ~x₂ \/ x₃) to:

• 3-coloring;
• 4-coloring;
• clique;
• subset sum problem;
• interval computations.

7-9. A straightforward algorithm takes time O(n) to compute the dot product of two vectors of size n.

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

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 Π₂P^Σ₄P.

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)?