Theory of Computations,
Test 3 for the course
CS 5315, Spring 2020

Name: _____________________________________________________

Up to 5 handwritten pages are allowed.

1. In the class, we proved that propositional satisfiability is NP-hard. Explain where in this proof did we use the two main physical assumptions:

2. Use the general algorithm to translate the formula (~a \/ b \/ ~c \/ d) & (a \/ ~b) into 3-CNF.

3-4. Use the corresponding reduction algorithms to reduce the satisfiability problem for the formula (~a \/ ~b \/ c) & (a \/ ~b) to:

In all these reductions, explain what will correspond to a = T, b = c = F.

5. Show how to compute the maximum of 11 numbers in parallel if we have an unlimited number of processors and we can ignore communication time. Why do we need parallel processing in the first place? If we take communication time into account, how much time do we need to compute the maximum of n numbers? Explain your answer. What is NC? Give an example of a P-complete problem.

6. What can you say about the Kolmogorov complexity of the following string: 010110111...011..1... all the way to 0 followed by 4000 1s. Explain your answer.

7. Suppose that we have a probabilistic algorithm that gives a correct answer 75% of the time. How many times do we need to repeat this algorithm to reduce probability of error to at most 0.1%? Explain your answer. Give an example of a probabilistic algorithm. Explain why we need probabilistic algorithms in the first place.

8. Use the variable-elimination algorithm for checking satisfiability of the following 2-SAT formula: (~a \/ ~b) & (~a \/ ~c) & (~b \/ ~c) & (~a \/ b) & (~c \/ b) & (a \/ b). Find all solutions.

9. How is "or"-operation represented in quantum computing? Provide a formula that described it for all possible inputs, and explain what will be the resulting state when one of the inputs is true, and another one is false.

10. Briefly describe what you have done for your project.