CS 5315, Test 2, Monday, May 6, 2013

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:

7-9. A straightforward algorithm takes time O(N2) to compute the sum of two matrices of size N X N.

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