**Name**

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

1-3.

- 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.
- For each of these four classes, explain whether this class
contains the problem of computing the
product a
_{1}* a_{2}* ... * a_{n}of n numbers. - For each of the above four classes, explain whether this class contains the main problem of interval computations.

4-7. Reduce the satisfiability problem for the formula
(x_{1} \/ x_{2}) & (~x_{1} \/
~x_{3}) & (x_{1} \/ x_{2} \/
~x_{3}) to:

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

8-12. A straightforward algorithm takes time O(n) to compute the product of n numbers.

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

13. Briefly describe your project for this class.

14. Briefly describe someone else's project for this class.