Computer Science 3650
Spring 2004
Solutions to additional questions for final exam

1. What is the definition of a polynomial time transformation from set A to set B?

   A polynomial time transformation from A to B is a function f such that

   1. f is computable in polynomial time;
   2. For every x, x is in A if and only if f(x) is in B.

2. What is the definition of an NP-complete problem?

   An NP-complete problem is a set Y with the following properties.

   1. Y is in the class NP.
   2. For every set X in NP, there is a polynomial time transformation form X to Y.

3. Is the vertex cover problem known to be NP-complete, or is that only conjectured? Is it known whether the vertex cover problem is in the class P? Is it known whether the vertex cover problem is in the class NP?

   The vertex cover problem has been proved NP-complete. It is not a conjecture.

   It is the consequences of being NP-complete that is the subject of conjecture. If P is different from NP, then no NP-complete problem is in P. But nobody knows whether P and NP are different classes of problems.

4. The partition problem is as follows. You are given a list of positive integers. You would like to create two sublists of the input list, with each number in exactly one of the sublists, so that the sum of the numbers in each sublist is the same. Describe a nondeterministic polynomial time algorithm for the partition problem.

   A nondeterministic algorithm is an evidence checker. You ask for evidence that the answer to a particular questions is 'yes', and you check whether the evidence is convincing.

   In the case of the partition problem, suppose that the input is a list x₁,...,x_n of n positive integers. The evidence is a list e₁,...,e_n of n 1's and 2's. The idea is that the evidence tells you how to partition the input list into two lists. If e_k is 1, put x_k into the first list. If e_k is 2, put x_k into the second list. To check the evidence, just check that the first and second lists have the same sum.

   This is a nondeterministic polynomial time algorithm, because it has the following characteristics.

   1. The checking phase (breaking the input list into two, according to the evidence, and then checking whether the two lists have the same sum) can easily be done in polynomial time. It takes time O(n) to do all of the work.

   2. If the input list can be partitioned into two lists that have the same sum, then there exists evidence that this checker will accept as good evidence. (The evidence is the correct split.)

   3. If the input list cannot be partitioned into two lists with the same sum, then there does not exist any evidence that this checker will accept. So the checker is not gullible.