Homomorphism erasing information
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


P=Closure( under log-space many-one reduction of, P)
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


NP=Closure( under log-space many-one reduction of, {SAT})
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.