CSCI 6420 Exercise set 4

CSCI 6420
Spring 2011
Exercise Set 4

Due. Monday, March 14 at the beginning of class.

Write clearly readable and well thought out answers to all of the following questions.

What is the definition of a polynomial time reduction between two languages?
What is the definition of class P?
What is the definition of class NP?
What is the definition of an NP-complete language?
A matching in an undirected graph is a set of edges such that every vertex is incident on exactly one of those edges. Think of the edges of the graph as representing possible pairings, and the problem is to select pairings so that each vertex belongs to one pair. Some graphs have matchings, but some do not.
Show that the following problem is in NP.

Input: An undirected graph G.

Question: Does G have a matching?
Imagine that you have a collection of bins, each able to hold a given maximum weight of material. You also have a collection of items that you want to put into the bins. You cannot break anything apart, and put part of it in one bin and part in another bin. You would like to know whether it is possible to put all of the items into the bins that you have, without exceeding any of the weight limits. To keep it simple, all of the bins have the same weight limit. The bin packing problem is as follows.
Input: (1) a positive integer L, which is the weight limit of each bin, (2) a positive number b that tells how many bins you have, and (3) a list of positive integers w₁, w₂, ..., w_k indicating the weights of k items to put into the bins.

Question: Is it possible to put all k of the items into the b bins (where each item is in exactly one bin) so that the total weight of items in each bin is no more than L?

Show that the bin packing problem is in NP.
The primality problem is the problem of reading a positive integer and saying whether it is prime. Is the following a polynomial time algorithm for the primality problem? Why or why not?
```
    prime(n)
    If n < 2 then
      answer no
    else
      for k = 2,...,n-1
        if n mod k = 0 then
           answer no
        end if
      end for
    end if
    answer yes
```

Classify each of the following sentences as either KT (known to be true), CT (true if standard conjectures are correct), KF (known to be false) or CF (false, if standard conjectures are true).
1. The satisfiability problem is NP-complete.
2. The satisfiability problem is in NP.
3. The satisfiability problem is in P.
4. The satisfiability problem is in NP-P.
5. All problems in NP reduce to the satisfiability problem in polynomial time.
6. There does not exist a (deterministic) polynomial time algorithm that solves the satisfiability problem.
7. The truth table algorithm for satisfiability is a polymomial time algorithm.

Review problems

Define A = {p | p(2) = yes}. Show that A is m-complete.

Define B = {p | p is a polynomial in a single variable x with integer coefficients and equation p(x) = 0 has a real-valued solution x}. Define C = {p | p is a polynomial of degree 2 with rational coefficients, and equation p(x) = 2 has a real-valued solution x}.
1. Show that C ≤_m B.
2. It is known that B is computable. Based on that, show that B ≤_m C.
Does {a} m-reduce to {}? That is, does there exist an m-reduction from the singleton set {a} to the empty set? Why or why not?

CSCI 6420 Spring 2011 Exercise Set 4

CSCI 6420
Spring 2011
Exercise Set 4