Due in class, March 23.
Sipser, exercise 7.16.
Sipser, exercise 7.22.
Sipser, exercise 7.28.
A homomorphism is a function h on strings with the property that h(xy) = h(x)h(y) (where juxtaposition is concatenation). A homomorphism is entirely defined by what it does to individual characters. For example, suppose that the alphabet is {a, b, c}. Define homomorphism H as follows on characters.
| H(a) = bbc |
| H(b) = a |
| H(c) = aaba |
When run on a string of characters, a homomorphism replaces each character by a string. For example, H(abc) = bbcaaaba. (The a has been replaced by bbc, the b has been replaced by a, and the c has been replaced by aaba.
A nonerasing homomorphism is a homomorphism h such that h(c) is not an empty string, for any character c. The example H shown above is nonerasing.
Although a homomorphism operates on a string, you can define what it means to compute a homomorphism of a set of strings: just compute the homormorphism of each thing in the set. So, if S is a set of strings, define
| h(S) = {h(x) \mid x \in S}. |
For example, let H be the homomorphism shown above. Then H({ab, bb, ca}) = {bbca, aa, aababbc}.
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 will use the term class for a set of sets of strings. For example, P and NP are classes, since a member of P is a set of strings. Say that a class C is {\it closed under nonerasing homorphisms\/} if, whenever S is a member of C and h is a nonerasing homorphism, the set h(S) is also in C.
Show that NP is closed under nonerasing homomorphisms. (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? Describe the nondeterministic polynomial time algorithm for deciding membership in h(S), using the nondeterministic polynomial time algorithm for S. Be careful about using a nondeterministic algorithm as a subroutine. Remember how nondeterministic algorithms work, by forking into a tree of computations, with the overall answer being yes just when there exists a thread that answers yes. Show how to build the new computation tree.)
Show that, if P = NP, then P is closed under nonerasing homomorphisms. (Hint. You have already done it. What does '=' mean?)
Show that, if P is closed under nonerasing homomorphisms, then P = NP. (Hint The difference between P and NP is one of information, or guesses. Although a nonerasing homomorphism 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.) Suppose that P is closed under nonerasing homomorphisms. 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 homomorphism $h$, you can arrange for h(CHECK) to be NP-complete. What information do you want to erase. (It is not the formula.))
Does anybody know whether P is closed under nonerasing homomorphisms?