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?
S is partially decidable if there exists a program p such that S = {x | phip(x) terminates}. (There are other equivalent definitions.)
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?
There are only finitely many possible configurations of an 8x8 chessboard. So there are only finitely many where black has a winning strategy. Every finite set is computable.
Is the set {p | phip(0) = phip(1)} decidable? Why or why not?
Call this set S. S is uncomputable because it satisfies the requirements of Rice's theorem.
S is nontrivial, since some programs p produce the same results on input 0 as they do on input 1 (take the program that computes function f(x) = 0) but some programs produce different results on 0 and 1 (take a program that computes function f(x) = x). So S is not empty, but it does not contain all programs.
S is a property of programs because, if p and q are two equivalent programs, the either both p and q are in S or both are not in S. (Equivalent programs produce the same result on every input. So if p and q are equivalent, then they compute the same (partial) function f. Either f(0) = f(1), in which case both p and q are in S, or f(0) is not equal to f(1), in which case both p and q are not in S.)
Is the set {(p,q) | p and q are equivalent programs} decidable? Prove your result.
Call this set A. A is uncomputable.
Proof. Let B be the set {r | phir(x) loops forever for every x}. Let L be a program that loops forever on every input. Notice that p is in B if and only if the pair (p,L) is in A, for every p. So function f(p) = (p,L) is a mapping reduction from B to A. But B is uncomputable by Rice's theorem. So A must also be uncomputable.
Let A = {p | phip(1) = 1} and B = {p | phip(1) = 2}. Show that A m-reduces to B.
The mapping reduction is f(p) = qp where qp is defined as follows.
qp(x)
1. Run p(x).
2. If the result from step 1 is 1
then produce answer 2.
else produce answer 1.
Now notice that phiqp(x) = 2
if and only if
phip(x) = 1,
for every x. That is,
q is in B if and only if p is in A.
So f is a mapping reduction from A to B.
Show that the set A from the preceding question is partially computable.
Write the following program Q.
Q(p)
1. Run p(1).
2. If the result of step 1 is 1
then halt
else loop forever
Notice that phiQ(p) halts just when p is in A.
That is, A = {p | phiQ(p) halts}. So, by the
definition of a partially computable set, A is partially computable.
Give an example of a set that is not partially computable. How do you know that it is not partially computable?
Let H be the halting problem set. The complement of H is not partially computable. If it were, then both H and its complement would be partially computable, and so H would be computable. But H is not computable.
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.
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.
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.
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 |
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.
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.)
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).
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.)
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.)
The reduction takes a list L that is an input to the partition problem and produces one of the following inputs to the subset-sum problem. Let R be the sum of all members of list L.
If R is even, then produce (L,R/2). That is, ask whether there is a sublist of L whose sum is R/2.
If R is odd, produce ((2), 1). That is, ask whether there is a sublist of the singleton list (2) whose sum is 1. (The answer is, or course, no.)
Notice that the answer to the input (partition) problem is the same as the answer to the output (subset-sum) problem. Also notice that the computation of the output can be done in polynomial time.
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?
Since the subset-sum problem is in NP, and the partition problem is NP-complete, there must be a polynomial-time mapping reduction from the subset-sum problem to the partition problem. (There is a polynomial-time mapping reduction from X to the partition problem for every set X that is in NP.)
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.
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.