Computer Science 3650
Summer 2004
Solutions to Practice Questions for Exam 3

This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.

  1. 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 is known to be NP-complete, and so it is also known to be in NP. But it is not known whether the vertex cover problem is in P. It is in P if and only if P = NP.

  2. What is the definition of the class P?

    P is the class of all decision problems that can be solved (deterministically) in polynomial time.

  3. What is the definition of the class NP?

    NP is the class of all decision problems that can be solved nondeterministically in polynomial time. That is, it is the problems that possess nondeterministic polynomial time algorithms.

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

    Let A and B be two sets. A polynomial time tranformation from A to B is a function F that has both of the following characteristics.

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

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

    A set A is NP-complete if both of the following are true.

    1. A is in NP.
    2. For every set X in NP, there exists a polynomial time transformation from X to A.

  6. 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. For example, if the input list is 2,2,3,4,5,7,9, then you can partition this into (2,2,5,7) and (3,4,9), each with sum 16. Notice that each number in the input list is present in exactly one of the two sublists. If a number is repeated, it must occur the same number of times total in the sublists.

    1. Express the partition problem as a set.

      Say that a list of numbers x1,...,xn is partitionable if there exists a subset I 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. The Partition Problem is the set {(x1,...,xn) | list x1,...,xn is partitionable}.

    2. Describe a nondeterministic polynomial time algorithm for the partition problem.

      Input: x1,...,xn.

      Evidence: A subset I of {1,...,n}.

      Check: Accept the evidence if the sum of xj for all j in I is equal to the sum of xj for all j not in I.

  7. The 0-1 Knapsack Problem is as follows. The input consists of a list of numbers x1,...,xn and a positive integer K. The question is whether there exists an index set I that is a subset of {1,...,n} such that the sum of xj for all j in I is exactly K.

    1. Express the 0-1 Knapsack Problem as a set.

      The 0-1 Knapsack problem is the set {((x1,...,xn), K) | there exists an index set I such that the sum of all xj for all j in I is equal to K}

    2. Show that there is a polynomial time transformation from the Partition Problem to the 0-1 Knapsack Problem.

      The transformation is function f defined as follows.

      1. If x1 + ... + xn is odd, then define f (x1,...,xn) = ((5,5),1). That is, choose the result to be an input to the knapsack problem whose answer is no. (You cannot find a sublist of (5,5) whose sum is 1.)

      2. If x1 + ... + xn is even, then define f (x1,...,xn) = ((x1,...,xn), (x1 + ... + xn)/2). That is, make the K value for the knapsack problem be half the total sum.

  8. Suppose that A and B are two sets that belong to the class NP. Show that the intersection of A and B is also a member of NP.

    Since A and B are both in NP, there must be nondeterministic algorithms for both A and B. Each has a kind of evidence and a checker. Devise a nondeterministic algorithm for the intersection of A and B as follows.

    Evidence: (e1, e2), where e1 is evidence of the correct form for A, and e2 is evidence of the correct form for B.

    Check: Accept (e1, e2) just when the checker for A accepts e1 and the checker for B accepts e2. Then we only accept evidence when it convinces us that the input is in A and the input is also in B.

  9. A simple path in a graph is a path that does not hit any vertex more than once. The Longest Path problem is as follows.

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

    Question: Is there a simple path in G that has length at least K?

    Show that the Hamilton Path problem can be transformed in polynomial time to the Longest Path problem.

    The Hamilton Path problem asks whether there is a simple path in a given graph that contains every vertex. To transform the Hamilton Path problem to the Longest Path, use function f (G) = (G,n) where n is the number of vertices in G. Notice that G has a Hamilton Path if and only if G has a simple path of length n.