How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

Question

In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps.

How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM? "Open question" is a fine answer.

Edit: removed the word "simulate" and replace with question about equivalent TMs for clarity, add below facts.

Here are some (uninteresting) related problems I do know bounds on:

• $DTIME_{1-tape}(O(n)){\subseteq}DTIME_{2-tape}(O(n))$. It's easy to make an equivalent 2-tape TM by ignoring one tape.
• There is a a $O(n)$ time 1-tape TM (recognizing $\{1^n\}$) that takes $O(n)$ time for any equivalent 2-tape TM to run.
• $DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$. This is the well-known method mentioned above, to simulate a 2-tape TM on a 1-tape TM.
• $DTIME_{1-tape}(O(n^2 logn)){\not\subseteq}DTIME_{2-tape}(O(n))$. Suppose every $O(n^2logn)$ time 1-tape TM ran in $O(n)$ time for some 2-tape TM. Then we would have $DTIME_{1-tape}(O(n^2logn)){\subseteq}DTIME_{2-tape}(O(n)){\subseteq}DTIME_{1-tape}(O(n^2))$ This would contradict known time hierarchy bounds for 1-tape TMs.

Answer 1

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy).

First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing machine that cannot be solved faster on a 2-tape TM would imply a major breakthrough.

On the opposite direction, one should be able to find a "universal" way to speed-up the simulation of a 1-tape TM on a 2-tape TM, but there are some examples for which the task seems hard; for example a 1-tape TM can efficiently simulate a dynamic non-linear system such as 1-D cellular automata - CA - (steps are parallel and use local information); and it is conjectured that the only way to know the state of the system after $n$ steps is to evolve the system $n$ times according to the rules (see e.g the (famous? :-) computational irreducibility - CIR - conjectured by S. Wolfram and analyzed in H. Zwirn and J.P. Delahaye, Unpredictability and Computational Irreducibility).

For example for every 1-D CA $A$ there is an $O(n^2)$ 1-tape TM $M_A$ that solves the problem:

Given a configuration $x$, is the state of $A$ equal to $x$ after $|x|$ steps from a blank initial configuration?

in $O(|x|^2)$ time.

Just use an expanded alphabet to overlap the target (input) configuration $x$, the current step evolving configuration and the next step configuration, and an extra bit for a "distributed" counter to stop the evolution after $|x|$ steps.

E.g.

x = 1 1 0 1 0 0 1  (target configuration)

x = [1 0 0 s ] [100s] [000s] [100s] [000s] [000s] [100s]
     | | | +-step counter
     | | +---next step CA configuration
     | +-----current step CA configuration
     +-------target configuration

The TM sweeps from left to right and apply the CA rules writing the new configuration in the "next step" bits. At the end of a sweep the role of the next/current bits are swapped. Furthermore, at every sweep it deletes an $s$, when no more $s$ it simply compares the current configuration to the target configuration.

There are not known ways to speed-up the simulation of a 1D CA on a k-tape TM, and (probably) such speed-up would imply that the Computation Irreducibility conjecture is false.