A simple trick that every complexity theorist should know but, based on some recent conversations, not every complexity theorist does know. Roughly speaking collapses for small resource bounds imply collapses for large resource bounds. Here is the result for NTIME (nondeterministic time) and DTIME (deterministic time) but the proof works for nearly every pair of complexity measures. **Translation Lemma:**Let f(n), g(n), h(n) be reasonable (time-constructible) functions with h(n)>n. ThenNTIME(f(n))⊆DTIME(g(n)) implies NTIME(f(h(n)))⊆DTIME(g(h(n))). The proof uses a technique known as padding. Let L be in NTIME(f(h(n))) via a machine M. Define A by

A = {x01 We can compute whether x01^{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). QEDAs 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.

--

Posted by Lance to Computational Complexity at 4/15/2005 08:41:00 AM