CSCI 6420
Spring 2009
Exercise Set 2

Due: Beginning of class on Monday, April 13.

  1. What is the definition of P?

  2. What is the definition of NP?

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

  4. Do there exist any problems that are neither in P nor in NP?

  5. Show that, if A and B are two sets that are in P, then the union of A and B is also in P.

  6. Show that, if A and B are two sets that are in NP, then the union of A and B is also in NP.

  7. Show that, if P = NP, then every set in NP over alphabet A except for the empty set and the set A* (the set of all strings over alphabet A) is NP-complete.

  8. A simple cycle in a graph is a cycle that contains no vertex more than once.

    The LONGEST-CYCLE problem is as follows.

    Input. An undirected graph G and a positive integer K

    Question. Does G have a simple cycle containing at least K vertices?

    Show that the LONGEST-CYCLE problem is NP-complete.

    (Hint. First show that the LONGEST-CYCLE problem is in NP. Then reduce the HAMILTON-CYCLE problem to it using a polynomial time reduction.)

  9. Define DOUBLE-SAT to be the problem of determining whether a CNF formula can be satisfied by at least two different vectors of values for the variables. Show that DOUBLE-SAT is NP-complete.

    (Hint: First show that DOUBLE-SAT is in NP. Then reduce 3SAT to DOUBLE-SAT. Your reduction can add new variables. Try to double the number of satisfying assignments.)

  10. If f is a CNF formula, then A NOT-ALL-EQUAL assignment (NAE-assignment) of values to variables is one such that every clause has at least one true literal and at least one false literal.

    NOT-ALL-EQUAL-3SAT (NAE-3SAT) is the following problem.

    Input. A 3-CNF formula f.

    Question. Is there a NAE-assignment of values for the variables of f? That is, is there an assignment of values to the variables in formula f so that each clause has at least one true literal and at least one false literal?

    Show that NAE-3SAT is NP-complete.

    Hint.

    1. First show that NAE-3SAT is in NP.

    2. Show that the negation of a NAE-assignment is another NAE-assignment.

    3. Show how to reduce 3SAT to NAE-3SAT in polynomial time. Create a new variable b and one variable for each clause. Call the variable for the i-th clause zi. Replace each clause (y1 \/ y2 \/ y3) by two clauses (y1 \/ y2 \/ zi) /\ (bar(zi) \/ y3 \/ b), where bar(zi) is the negation of zi. Do not just assume this works. Show that it does.