**Translation Lemma:** Let f(n), g(n), h(n) be reasonable (time-constructible)
functions with h(n)>n. Then

The proof uses a technique known as padding. Let L be in NTIME(f(h(n))) via a machine M. Define A by

^{h(|x|)-|x|-1}| x in L}

^{h(n)-|x|-1}is in A by simulating M(x) which takes nondeterministic time f(h(|x|))=f(m) where m=h(n) is the length of the input. So A is in NTIME(f(m)) and by assumption in DTIME(g(m)).

Now if we want to compute whether x is in L we can use the DTIME(g(m)) algorithm for A on x01

^{h(n)-|x|-1}taking total time g(h(n)) since the input has size m=h(n). QED

As an immediate consequence we get that if P=NP then E=NE (where
E=DTIME(2^{O(n)})) by letting h(n)=2^{n}.

The translation lemma works in only one direction. You need h(n)>n, you can't unpad an arbitrary x. It's open whether E=NE implies P=NP for instance.

The lemma has many applications. Here is one example.

**Theorem:** If P=NP then some language in E does not have
subexponential-size circuits.

**Proof:** In the Σ_{4} level of the E-time hierarchy
we can compute the
lexicographically-first language A that cannot be simulated by any
2^{n/2}-size circuits. If P=NP then the polynomial-time
hierarchy collapse to P. By
a version of the translation lemma with h(n)=2^{n} the
polynomial-time hiearchy collapsing to P implies
the E-time hierarchy collapses to E. Thus A is in E
but A does not have subexponential-size circuits.

It seems that the proof here assumes g(n) > n...

ReplyDelete