Test 3, Tuesday, May 5, 2015
(Please do not forget to put your name on all
extra sheets of paper)
- 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 \/
- subset sum problem;
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
13. Briefly describe your project for this class.
14. Briefly describe someone else's project for this class.