Computational Complexity

Tuesday, March 22, 2005

 
Tape Reduction

Posted by Lance

Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoteric question, tape reduction plays an important role in time and space hierarchies and creating efficient reductions.

For space we have an easy result: Every k-tape s(n)-space bounded Turing machine can be simulated by a 1-tape machine in O(s(n)) space. Create a single supertape with separate "tracks" for each of the original tapes and add markers for the locations of the heads on each of these tapes.

For deterministic and nondeterministic time, this constructions yields a t²(n)-time 1-tape simulation of a k-tape t(n)-time machine and this is the best you can do (consider { x#x | x∈Σ^*}). We can do much better if we reduce k tapes to 2 tapes.

We can simulate any nondeterministic t(n)-time k-tape machine in nondeterministic O(t(n)) time on a 2-tape machine. Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

For deterministic time we can only achieve a weaker result: Every t(n)-time k-tape machine has a 2-tape simulation using O(t(n)log t(n)) time. The proof (due to Hennie and Stearns) is quite involved and I won't give it here. The proof has a nice side effect: The construction creates an oblivious machine where the head movements depend only on the input length. One can use this fact to show that we can simulate any t(n)-time Turing machines with O(t(n)log t(n))-size bounded fan-in circuits and reduce any t(n)-time nondeterministic computation to satisfiability questions of size O(t(n)log t(n)).

3:05 PM #

1.  Anonymous says:  
   
   Lance, there was a post you made about a prospective theory grad student's view of the different theory groups which I cannot seem to find anymore. Has it been censored because it was sensitive?
   

   1:47 PM, March 23, 2005

2.  Anonymous says:  
   
   A google search for "nuki + livejournal" will lead to the blog.
   

   7:30 PM, March 23, 2005

3.  Anonymous says:  
   
   Are results known for any other measures than time and space?
   

   2:41 AM, March 24, 2005

4.  Anonymous says:  
   
   is there any hardness result known regarding whether a t(n)-time k-tape machine can be simulated by a O(t(n))-time 2-tape machine?
   --Mohammad
   

   4:23 PM, March 25, 2005