CSCI 4602
Fall 2000
Practice questions for quiz 5

See homework exercises 13 for some practice questions. Here are some additional questions.

  1. Describe the error in the following fallacious "proof" that P is different from NP.

    A formula of length n can have at least sqrt(n) different variables. It is satisfiable if some assignment of values to those variables makes it true. But there are 2sqrt(n) assignments of values to the variables, and trying them all takes at least 2sqrt(n) steps. Since 2sqrt(n) grows faster than any polynomial, SAT is not solvable in polynomial time. So SAT is not in P. But SAT is in NP, so P and NP are clearly different classes.

  2. The class DP lies between NP and PSPACE. There is a notion of a DP-complete problem. Define a DP-complete problem in a reasonable way, using the notions of completeness for classes that we have used.

  3. Define C to be the class consisting of all problems that are either in P or are NP-complete. Suppose that P and NP are different classes. Are there any problems in NP that are not in C?

  4. It is not always obvious whether a problem is difficult or easy to solve. Consider the following two problems.

    Problem 1. The input consists of three integers a, b and c. The question is, do there exist positive integers x and y such that ax2 + by = c?

    Problem 2. The input consists of two integers aand c. The question is, does there exist a positive integer x such that ax2 = c?

    Problem 2 has efficient algorithms, but no efficient algorithm is known for problem 1. How, in general terms, might you go about identifying a problem that is difficult to solve, and distinguish it from a problem that is easy to solve?