CS 5315, Test 2, Monday, April 25, 2011


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

1. Define 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 propositional satisfiability problem? The problem of sorting a given array?

2-6. Reduce the satisfiability problem for the formula (x1 \/ x2) & (~x1 \/ ~x2) & (~x1 \/ x2 \/ x3) to:

Use a greedy algorithm to find a solution to the original satisfiability problem.

7-9. A straightforward matrix multiplication algorithm takes time O(n^3) to compute the product of two square 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 Π2PΣ4P.

12. Which class of the polynomial hierarchy corresponds to optimization?