2
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • $\begingroup$ Why is the two letter restriction important for you? It is not explicitly in the exercise. $\endgroup$
    – Hendrik Jan
    Commented Sep 6, 2014 at 10:28
  • $\begingroup$ Yes, there's no such restriction in the book, but without it the whole exercise is rather trivial. I thought the whole difficulty lies in it, but maybe you have right and I'm exaggerating. By the way, that is suspicious why the 0-1 alphabet introduce such limitation. $\endgroup$
    – Adam Przedniczek
    Commented Sep 6, 2014 at 11:11

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.