CSCI 6420
Spring 2004
Solutions to 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?

    Problem X is DP-complete if X is in DP and, for every Y in DP, Y mapping-reduces to X in polynomial time.

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

    It is a theorem that SAT is NP-complete. It is not just a conjecture.

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

    If P and NP are different then there does not exist a polynomial time algorithm to solve the vertex cover problem, since the vertex cover problem is NP-complete.

  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.

    2L(n) = 2log(n)*log(n) = (2log(n))log(n) = nlog(n). This is n to an exponent that grows without limit as n grows. It is clearly larger, in the limit, than nk for any fixed k.

  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.)

    The limit as n goes to infinity of n5log(n5)/n6 is equal to the limit as n goes to infinity of log(n)/n, which is 0. All polynomials are time-constructible. Since n6 is a time-constructible function, the hierarchy theorem tells us that TIME(n5) is a proper subset of TIME(n6).

  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.

    A certificate is the partitioning itself. Given two lists of numbers, it is easy to check that their sums are equal and that, when combined, they produces the same list as the input list to the problem. (Sort the input list and the combination of the two lists in the certificate, and see whether they are the same.)

  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 course time assignment problem is in NP. A certificate is an assignment of courses to time slots. To check the certificate, check that each student's list of courses has no time conflicts, and that only the available number of time slots have been used.

    The graph colorability problem is as follows.

    Input: An undirected graph G and a positive integer K.

    Question: Is it possible to color the vertices of G using no more than K colors (coloring each vertex just one color) so that no two adjacent vertices have the same color?

    The graph colorability problem reduces to the course assignment problem via reduction defined as follows. Given graph G and positive integer K, produce a course assignment problem whose courses are the vertices of G, and with K available time slots. Include, in the problem, a student for each edge of G. The student associated with edge (u,v) wants to take courses u and v, and nothing more.

    Suppose that G can be colored with K colors. Get a K-coloring of G. Assign times slots to the courses by following the coloring. If vertex v is colored by color m, then use time slot m for course v. Since the coloring does not color any two adjacent vertices the same color, there can be no time conflicts.

    Suppose that the courses can be assigned time slots so that there are no conflicts. Then assign colors to G in the same way, using the m-th color for vertex v if course v received the m-th time slot. Since there is a student for each edge, and none of the students have time slot conflicts, this coloring must avoid coloring two adjacent vertices the same color.

    Remark. Be sure that your reduction goes the right direction. You need to show how to solve the graph coloring problem, assuming that you already have a solution to the course assignment problem, not the other way around.

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.

      Suppose that P = NP. Since P is a deterministic complexity class, it is closed under complementation, so P = Co-P. So P = Co-NP, and NP = Co-NP = P. Taking the contrapositive of this, if NP =/= Co-NP then P =/= NP.

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

      Suppose that X is NP-complete, and let Y be the complement of X. Since X is in NP, Y is in Co-NP, by the definition of Co-NP. Let L be an arbitrary problem in Co-NP, and let M be the complement of L, which must be in NP. Since X is NP-complete, every problem in NP reduces to X in polynomial time. Since M is in NP, there must be a polynomial-time computable function f such that

      x is in M <==> f(x) is in X
      But, because L is the complement of M and Y is the complement of X,
      x is not in L <==> f(x) is not in Y
      But you can negate both sides of a equivalence, yielding
      x is in L <==> f(x) is in Y
      So the same function f reduces from L to Y. Since L is an arbitrary problem in Co-NP, every problem in Co-NP reduces to Y in polynomial time.

  2. Explain why PTQBF = NPTQBF.

    PTQBF = PSPACE because TQBF is PSPACE-complete. (To show PTQBF is a subset of PSPACE, just replace the TQBF oracle by an algorithm that solves TQBF in polynomial space. To show that PSPACE is a subset of PTQBF, use the fact that TQBF is PSPACE-complete, and solve an arbitrary problem in PSPACE by reducing it to TQBF.)

    NPTQBF = NPSPACE by similar reasoning.

    But, since PSPACE = NPSPACE, PTQBF = NPTQBF.

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

    It suffices to show how to solve a Co-NP-complete problem. The complement UNSAT of SAT is Co-NP-complete. Solve UNSAT by asking the SAT oracle whether a given formula F is satisfiable. If the formula is satisfiable, answer that F is not in UNSAT. If F is not satisfiable, answer that F is in UNSAT.

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

    PTQBF = PSPACE and NP is a subclass of PSPACE, so we are done.

  5. What is the inverse of 4 mod 9?

    The inverse of 4 mod 9 is 7. Notice that 4*7 = 28, and 28 mod 9 = 1, so 4*7 = 1 (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?

    The mechanism is to reduce the problem of factoring n to the problem of computing discrete square roots mod n. The reduction that we did was probabilistic; it gets an answer in expected polynomial time.

  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?

    n = pq = 55
    phi(n) = (p-1)(q-1) = 40
    e = 3 (in fact, e can be chosen to be any value such that gcd(e, (p-1)(q-1)) = 1. A good choice is the smallest such value.)
    d = 27. (Notice that ed = 81, and 81 mod 40 = 1.)

    The encoding and decoding functions are

    E(x) = x3 mod 55
    D(x) = x27 mod 55

  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?

    We think that anyone trying to break the code does not have enough time to break it, because the problem of breaking the code is a complex one.