[Solved]: Homomorphism erasing information

ignougroup
Problem Detail: I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser’s Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under nonerasing homomorphism (replacing all characters with nonempty string), then P = NP. With nonerasing homomorphism I cannot delete the characters, but I can get rid off the information by overwriting it e.g. with 0s. I’m trying to complete the following idea:

  1. Checking whether a given assignment to propositional formula makes it true is in P class. Let s be the 0-1 string encoding both the formula and particular assignement.
  2. I’m trying to find such nonerasing homomorphism H over 0-1 alphabet that H applied to string s will erease (overwrite with something that will destroy information) the particular variables assignment but I must be able to read off the formula.

Have anyone the idea how such a homomorphism could look like? (only 2 letter alphabet is allowed).

Asked By : Adam Przedniczek

Answered By : Thomas Klimpel

Denote the closure of a class C of languages under log-space many-one reductions by Closure( under log-space many-one reduction of, C), and the closure of a class C of languages under e-free homomorphisms by Closure( under e-free homomorphisms of, C). So for example

  • NP=Closure( under log-space many-one reduction of, NP)
  • NP=Closure( under e-free homomorphisms of, NP)

We want to show:

If P=Closure( under e-free homomorphisms of, P) then P=NP.

For this, it is sufficient to show

  1. P=Closure( under log-space many-one reduction of, P)
  2. NP=Closure( under log-space many-one reduction of,
    Closure( under e-free homomorphisms of, P))

because if P=Closure( under e-free homomorphisms of, P) then
NP=Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))
=Closure( under log-space many-one reduction of, P)=P It is well known how to show (1). For showing (2), it is sufficient to show

  1. NP=Closure( under log-space many-one reduction of, {SAT})
  2. SAT $in$ Closure( under e-free homomorphisms of, P)

because if X$subset$Y then Closure( under … of, X)$subset$Closure( under … of, Y). It is well known how to show (3), which says that SAT is NP-complete under log-space many-one reductions. For showing (4), note that certificates of length O(n) are sufficient for SAT, where n is the length of the input. So we need to show that e-free homomorphisms can erase a certificate of length O(n) from the input, if the certificate is encoded suitably. This is straightforward in a certain sense, but we have to change the alphabet. The letters of the larger alphabet contain both an original input letter, and an additional certificate letter. To “erase the certificate”, the homomorphism replaces this pair of “(original letter, certificate letter)” by the “original letter”. If you want to stay with the 0-1 alphabet, then homomorphisms from the free monoid over 0-1 can’t erase information selectively enough, because such a homomorphism is already uniquely determined by the image of 0 and 1. But if you look instead at the submonoid of words whose length is a multiple of some number k, then you can easily find suitable homomorphisms.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29698  Ask a Question  Download Related Notes/Documents