Due: Beginning of class on Monday, April 13.
What is the definition of P?
What is the definition of NP?
What is the definition of an NP-complete problem?
Do there exist any problems that are neither in P nor in NP?
Show that, if A and B are two sets that are in P, then the union of A and B is also in P.
Show that, if A and B are two sets that are in NP, then the union of A and B is also in NP.
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.
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.)
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.)
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.
First show that NAE-3SAT is in NP.
Show that the negation of a NAE-assignment is another NAE-assignment.
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.