Due. Monday, March 28 at the beginning of class.
Write clearly readable and well thought out answers to all of the following questions.
Do there exist any problems that are neither in P nor in NP?
Suppose that A and B are two languages where B is in NP and A is a subset of B. Is A necessarily in NP?
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?
The HAMILTON-CYCLE problem is as follows. It is known to be NP-complete.
Input. An undirected graph G
Question. Does G have a simple cycle containing all of its vertices?
Using the fact that the HAMILTON-CYCLE problem is NP-complete, show that the LONGEST-CYCLE problem is NP-complete.
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.
The negation of an assignment of values to variables is one where you negate the values of all of the variables. 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) /\ (not(zi) \/ y3 \/ b), where not(zi) is the negation of zi. Do not just assume this works. Show that it does.
You will encounter a difficulty in showing that it works. Bring in your result from part (b). If the assignment you are looking at is not suitable, consider its negation.
A nonerasing homomorphism (NEH) is a function that takes a character and produces a nonempty string. For example, you might define NEH h over alphabet {a,b,c} by h(a) = cb, h(b) = a and h(c) = bcb. You define how a NEH h works on strings by letting it replace each character separately by a string. Using our example h, h(ab) = cba (where the a has been replaced by cb and the b has been replaced by a), h(cc) = bcbbcb and h(cab) = bcbcba.
If L is a language and f is a function that takes a string and yields a string, define f(L) = {f(x) | x in L}. That is, f(L) contains the image under f of every member of language L.
There is a notion of closure of sets under functions. The set of integers is closed under the function f(x) = 2x since, whenever x is an integer, 2x is also an integer. The set of integers is not closed under function g(x) = x/2 since g(1) is not an integer.
We need to look at languages instead of numbers. A class C of languages is closed under function f if, for every language L in class C, f(L) is also in C.
Show that NP is closed under NEHs. (Hint. Suppose that S is in NP. Then there must be a nondeterministic polynomial time algorithm that takes an input x and tells you whether x is in S. You need to find a nondeterministic polynomial time algorithm to decide whether a given string y is in h(S). But y is in h(S) just when there exists a string x such that x is in S and y = h(x). How does the length of x compare to the length of y? Can it x be longer than y? Describe a nondeterministic polynomial time algorithm for deciding membership in h(S), using the nondeterministic polynomial time algorithm for S.)
Show that, if P = NP, then P is closed under NEHs. (Hint. You have already done it. What does '=' mean?)
Show that, if P is closed under NEHs, then P = NP. (Hint. The difference between P and NP is one of information (the evidence). Although a NEH cannot erase characters, it can erase information. (You can wipe out the information on a disk by replacing every bit by 0. You did not remove any of the bits, but the information is gone. When you type a password into a box, you typically see an asterisk for each character.) Suppose that P is closed under NEHs One problem that is in P is the problem of checking whether a particular assignment of truth values to variables makes a propositional formula true. Let CHECK be this truth-checking problem. Show that, by stating the truth-checking problem appropriately, and choosing an appropriate NEH $h$, you can arrange for h(CHECK) to be NP-complete. What information do you want to erase? (It is not the formula.))
Conclude that P = NP if and only if P is closed under NEHs.
Does anybody know whether P is closed under NEHs?