CSCI 6420
Computability and Complexity
Section 001
Spring 2013

Last modified: 3/26/13

Announcements


Syllabus

See the syllabus for a description of the course.


Homework

Due Wednesday, Apr. 2. Sets in NP have easy-to-check proofs of membership. Sets in CoNP have easy-to-check proofs of nonmembership. Sets in the intersection of NP and CoNP have both. Show that, if NP is not equal to CoNP, then SAT is not in the intersection of NP and CoNP. So SAT does not have easy-to-check proofs of nonmembership.

Due Monday, April 29. Prove that P = NP if and only if P is closed under nonerasing homomorphisms.

Recall that a homorporphism on strings is a function that takes a string and yields a string, with the property that, for every x and y, h(xy) = h(x)h(y). A nonerasing homorphism also has the property that, if x is not an empty string then h(x) is also not an empty string. Saying that P is closed under nonerasing homomorphism means that, for any nonerasing homomorphism h and any set A in P, the set h(A) = {h(x) | x in A} is also in P.

Hint. First prove that, if P = NP then P is closed under nonerasing homorphisms. Just create a nondeterministic polynomial time algorithm for h(A), for any given set A in P and any given nonerasing homomorphism h. Notice that y is in h(A) if and only if there exists an x in A so that y = h(x).

Next, show that if P is closed under nonerasing homorphisms then P = NP. It suffices to find a set A that is in P so that h(A) is NP-complete. What if you include a certificate for an NP-complete problem as part of the input? Can you arrange for the homormorphism to erase the information content of the certificate? (Think about typing a password into a box. You type the password, and all you see in the box is a sequence of asterisks.)


Office hours and my home page

Office hours are MW 2:00–3:00 and TTh 1:30–3:00. My home page is www.cs.ecu.edu/~karl/.