**Name**

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

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 sum of two matrices? the 4-coloring problem?

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

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

7-9. A straightforward algorithm takes time O(N^{2}) to
compute the sum of two matrices of size N X 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/2, how many times do we need to repeat it to reduce the probability of error to 0.1%?

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

12. Which class of the polynomial hierarchy corresponds to finding the best alternative -- i.e., an alternative x for which objective function f(x) attains the largest possible value?

13. What is the Kolmogorov complexity of a sequence 010010 ... 010 (repeated 2,013 times)?