Computational Complexity

Friday, April 15, 2005

 
The Translation Lemma

Posted by Lance

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

NTIME(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^h(|x|)-|x|-1 | x in L} We can compute whether x01^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ⁿ.

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 Σ₄ 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ⁿ 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.

8:41 AM #

1.  Anonymous says:  
   
   It seems that the proof here assumes g(n) > n...
   

   9:41 PM, May 04, 2005

Comment Feeds: This Post All