CS 5315, Test 3, Tuesday, May 5, 2015

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 a1 * a2 * ... * an 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 (x1 \/ x2) & (~x1 \/ ~x3) & (x1 \/ x2 \/ ~x3) 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.