CS 5315, Test 2, Wednesday, April 30, 2014

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 dot product (a, b) = a1 * b1 + ... + an * bn of two vectors a = (a1, ..., an) and b = (b1, ..., bn) of size n? the main problem of interval computations?

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) 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 Π2PΣ4P.

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