CSCI 6420
Spring 2004
Practice questions for exam 2

You will be tested again on material from complexity theory. The following are repeated from the last group of practice questions.

  1. DP is a complexity class that lies between NP and PSPACE. That is, NP is a subset of DP and DP is a subset of PSPACE. DP-complete problems are defined in the usual way for classes in this region of complexity. What is the definition of a DP-complete problem?

  2. Is it known that the satisfiability problem is NP-complete, or is that only a conjecture?

  3. If P and NP are different, what can you say about the time required to solve the vertex cover problem?

  4. For this problems all logarithms are base 2. Let L(n) = (log n)2. Argue that an algorithm that takes time 2L(n) on inputs of length n does not run in polynomial time. You will find the following facts useful.
    x(yz) = (xy)z
    2log(n) = n
    The second equation is the defining equation for the log function.

  5. Prove that TIME(n2) is a proper subset of TIME(n3). (All polynomials with integer coefficients are time constructible. You do not need to prove that.)

  6. (Note: this problem has been made easier.) The partition problem is as follows.

    Input: A list of positive integers x1, ..., xn.

    Question: Does there exist an index set I that is a subset of {1, ..., n} such that the sum of all xj for j in I is equal to the sum of all xj for j not in I. That is, can you partition the input list into two separate lists that have the same sum?

    Show that the partition problem is in NP.

  7. The course time assignment problem is as follows.

    Input: A set of students S, a set of classes C a positive integer K and, for each student s in S, a list of courses that student s wants to take.

    Question: Is it possible to schedule courses into only K time slots so that it is possible for each student to take all of his or her desired courses, without any time conflicts?

    Prove that the course time assignment problem is NP-complete.

    Hint: Reduce from the graph colorability problem. (Read about this.) Think of the courses as vertices of a graph, and put an edge between two courses if they cannot be scheduled in the same time slot.

The following are additional questions.

  1. Co-NP is the class of the complements of the problems in NP. For example, since SAT is in NP, its complement {x | x is a formula that is not satisfiable} is in Co-NP. Co-NP-complete problems are defined in the usual way.

    1. It is not known whether or not Co-NP and NP are the same classes of problems. Show that, if NP and Co-NP are different, then P and NP are also different. (Hint: Suppose that NP and Co-NP are different. Reason that P and NP must also be different by contradiction. Notice that P is closed under complementation.) Give a clearly reasoned proof, not just a rehash of the hints.

    2. Show that, if problem X is NP-complete, then the complement of X is Co-NP complete.

  2. Explain why PTQBF = NPTQBF.

  3. Show that Co-NP is a (not necessarily proper) subclass of PSAT

  4. A problem X is said to be NP-hard if NP is a subclass of PX. Show that TQBF is NP-hard.

  5. What is the inverse of 4 mod 9?

  6. Computing discrete square roots mod n, where n is the product of two primes, is as hard as factoring n. What mechanism is used to show that?

  7. If primes p = 5 and q = 11 are chosen, what are the private and public keys selected for the RSA system? What are the encoding and decoding functions?

  8. In public key (two-key) cryptography, we give away enough information to break the encryption. What makes us think that nobody can make effective use of that information?