Computer Science 6420
Spring 2004
Practice Questions for Exam

  1. Let S be a set of strings. What does it mean for S to be computable? What does it mean for S to be partially computable?

  2. A configuration of pieces on an 8x8 chessboard can be described by a string. The configuration tells which piece (if any) is in each square, and whose move is next. Consider the set W of all chessboard configurations where black has a winning strategy. Is W decidable?

  3. Is the set {p | phip(0) = phip(1)} decidable? Why or why not?

  4. Is the set {(p,q) | p and q are equivalent programs} decidable? Prove your result.

  5. Let A = {p | phip(1) = 1} and B = {p | phip(1) = 2}. Show that A m-reduces to B.

  6. Show that the set A from the preceding question is partially computable.

  7. Give an example of a set that is not partially computable. How do you know that it is not partially computable?

  8. 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?

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

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

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

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

  13. 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?

    1. Show that the partition problem is in NP.

    2. Show that the partition problem polynomial-time reduces to the subset-sum problem. (See Sipser, page 268, for the definition of the subset-sum problem.)

    3. Both the partition problem and the subset-sum problem are known to be NP-complete. Based on that knowledge, can you say whether there is a polynomial-time reduction from the subset-sum problem to the partition problem?

  14. The course time assignment problem is as follows.

    Input: A set of students S, a set of courses 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, which is as follows, and is known to be NP-complete. The input is an undirected graph G and a positive integer K. You have K different colors of paint, and you will paint each vertex one color. The question is whether it is possible to color the vertices so that now two adjacent vertices are painted the same color.

    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. Fill in the details and show that this works.