31
$\begingroup$

If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

We haven't this kind of overhead for NTIME of DSPACE. A basic justification comes from the details of the proof by considering the difference between simulators.

My question is the following: without considering the detail of the proof of DTIME hierarchy theorem, is there a justification of this log or it could be just a consequence of the proof and it would be reasonable to imagine that if $f = o(g)$ then

$DTIME(f) \subsetneq DTIME(g)$

In my opinion, considering that the simulation explanation is a good justification should be itself justified by proving that if we had a better result, then we could create a better simulation.

$\endgroup$
6
  • 5
    $\begingroup$ I think that what you wrote in the last paragraph is less likely than its opposite. Namely, I do not think that we can currently rule out the possibility that a stronger statement can be proved by a method other than simulation. On the other hand, we might be able to rule out the possibility that a stronger statement can be proved by simulation by constructing a relativized world where the stronger statement fails. $\endgroup$ Mar 6, 2011 at 4:22
  • $\begingroup$ As far as I understand, reducing the $\Omega(\log n)$ simulation overhead in the deterministic time hierarchy theorem would be a breakthrough result. For one thing, several results could be immediately strengthened. $\endgroup$ Mar 6, 2011 at 21:24
  • 4
    $\begingroup$ This is somewhat pedantic, but unless you have further additional restrictions on f and g (the standard one would be f and g being time-constructible), there exist f and g such that f=o(g), and DTIME(f)=DTIME(g). To see this, just consider the uncountable set of of all functions x^i, with i real, 0 < i <= 1. If the Time Hierarchy Theorem was true for all pairs of such functions, then we would get an uncountable set of languages, all decidable by Turing machines. This contradicts the fact that the set of Turing machines is countable. $\endgroup$ Mar 7, 2011 at 2:06
  • 1
    $\begingroup$ @abel I assume of course that f and g are time-constructible, like in current time hierarchy theorem. $\endgroup$ Mar 8, 2011 at 1:22
  • $\begingroup$ yes there is a justification looking at the current proof, but a full answer to this problem/question would prove its necessary and not merely sufficient. ie as AS comments above, a tighter bound is an open problem. in hopcroft/ullman 1976 they point out the log(n) factor is due to reducing a multitape TM into a 2-tape TM and also have the relevant proof for that reduction. (along with this question however, have always wondered how the hierarchy thms would look different for a complexity theory based on single tape TMs instead of one that allows multitape TMs. seems related to this question) $\endgroup$
    – vzn
    Aug 20, 2012 at 2:18

3 Answers 3

5
$\begingroup$

The time hierarchy theorem is the subject of my diploma project, perhaps you want to view the comments on my question Lower bounds and class separation .

Looking back to this question and how it relates to what you are asking, I got an idea that might show that the multitape to single tape TM simulation overhead needed by the theorem's proof cannot be improved. Thus, another approach is needed if we wish to improve this result.

EDIT: This proof is incorrect, see the comments below for the exact reason. I am currently editing the answer to reflect that.

Let $A$ be the language $ \{ 0^{k}1^{k}| k \geq 0 \}$ .

On a single tape machine, there is an $O(n \log n)$ algorithm (you can find details of this algorithm in chapter 7.1.2 of Sipser's book "Introduction to the Theory of Computation). In the same reference, you can see that a language is in o(n \log n) if and only if it is regular. Kaveh also provides the original papers for this claim in the question linked above.

In the comments of my question, Ryan Williams illustrates an $O(n)$ algorithm for the same problem, using a 2-tape TM.

Assume now that there is a technique for simulating a multitape TM into a single tape TM that has a running time of $ o( T(n) \log T(n) ) $, where $T(n)$ is the running time of the TM simulated. By applying it to the machine Ryan illustrates, we would get a single tape TM that would run in $ o( n \log n) $. Therefore, $A$ is regular , which is a contradiction. So, we conclude that an overhead of $ \log T(n) $ is the best we can do when simulating multi tape machines with single tape machines.

I realize this is a strong statement, so I might be wrong in my interpretation.

Even if a technique exists that allows to improve this result, I believe that it is not possible to match the result for $NTIME$ or $SPACE$. My intuition derives by the following fact:

There is a very known result that states $DTIME(n) \neq NTIME(n)$. Under the assumption that $ P \neq NP$ I believe this result is improved to $ DTIME(n^{k}) \neq NTIME(n)$ , for any $k$.So, a very small non-deterministic class is much more powerful than any deterministic. So, given how powerful a resource non-deterministic time is, I would expect that a greater amount of deterministic time would be needed to make a TM more powerful to compensate for non-determinism's power.

$\endgroup$
3
  • 10
    $\begingroup$ It takes quadratic time to simulate a multi-tape Turing machine on a single-tape machine. The language of palindromes shows that this is necessary: palindromes can be recognized in $O(n)$ time on two-tape machines, but it takes time $\Omega(n^2)$ on single-tape machines $\endgroup$ Mar 7, 2011 at 16:35
  • $\begingroup$ Luca is of course correct (I expected a mistake due to the strength of the statement). My fault: I hastily confused the standard single-tape TM with the single work-tape (with different non-write input tape and perhaps a separate output tape). When I realized the mistake, I tried to see if the $o(n \log n)$ regularity carries to that model, but $PALINDROMES$ show that it is not true. I am editing the answer to reflect this fact, I hope the asker @Monoid accepted it for the intuition part. $\endgroup$
    – chazisop
    Mar 8, 2011 at 18:03
  • $\begingroup$ The example Luca mentions is for a case where time is $o(n^2)$. This particular case is troubling in general because of the non-robust behavior of single-tape machines in such small classes. So it is not an obstacle if the time is $\Omega(n^2)$. Interestingly the proof of the strong version of the hierarchy theorem for $o(n^2)$ doesn't use simulation but a direct argument (see Hartmanis 1968). $\endgroup$
    – Kaveh
    Aug 17, 2012 at 16:09
10
$\begingroup$

For n-tape TMs a tight time hierarchy result similar to the space hierarchy theorem is proven by Furer in 1982. The $\lg$ factor is not needed.

The $\lg$ factor for the time hierarchy theorem stated in your post is only for single-tape TMs. Unless you are very committed to the single-tape model for some reason there is not a difference between space and time regarding the hierarchy theorems.

There are some reasons and arguments for using single-tape TMs for defining time complexity classes, but the usage of single-tape TMs for defining complexity classes is not universal, e.g. see Lance Fortnow and Rahul Santhanam's [2007] where they use multiple-tape TMs.

The original reference for the time hierarchy theorem is Hennie and Stearns [1966]. They prove the theorem for two-tape machines. Odifreddi's Classical Recursion Theory cites them and Hartmanis [1968] and describes a proof that looks similar to the one in Sipser's book.

However the proof for single tape TMs in Hartmanis's paper does not use simulation simply. It distinguished between two cases: 1. running-time being $\Omega(n^2)$ and 2. running-time being $o(n^2)$.

  1. For the first case it uses a simulation, and it seems that one can get rid of the $\lg$ factor if the simulations can be done more efficiently.

  2. For the second case, the paper directly gives a language for the separation and doesn't use simulation at all. This uses particular properties of single-tape TMs with sub-quadratic running-time.

One should note that single-tape TMs with time $o(n^2)$ are not as robust and there are quadratic lowerbounds (e.g. for Palindroms) on single-tape TMs whereas a two-tape TM can solve such problems in linear time.

As I said above, unless you are committed to single-tape TM model for some reason, even when time is sub-quadratic, there is not a gap to fill, the time hierarchy theorem is as tight as possible.

PS: if we are using multiple-tape TMs, i.e. a Turing machine in the class can have fixed but arbitrary number of tapes Fürer's result does not apply.

  1. Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
  2. Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999 (page 84)
  3. Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
  4. F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
  5. Lance Fortnow and Rahul Santhanam's paper "Time Hierarchies: A Survey", 2007
$\endgroup$
3
  • 4
    $\begingroup$ Doesn't Fürer's result only apply to the case when the number of tapes of the Turing machines under consideration is fixed, i.e, talks about classes $DTIME_k(f)$, $k$ being the number of tapes. $\endgroup$ Jan 30, 2013 at 13:24
  • $\begingroup$ @Markus, yes, that is correct, it is similar to the single-tape case. The only difference is that the number of tapes is more than one, but it is still fixed, e.g. 2 tapes. $\endgroup$
    – Kaveh
    Jan 30, 2013 at 16:17
  • $\begingroup$ See also Krzysztof Loryś, "New time hierarchy results for deterministic TMs", 1992. Another reference is Kazuo Iwama, Chuzo Iwamoto, "Improved time and space hierarchies of one-tape off-line TMs", 1998, which improves the log factor to log log for single-tape TMs. $\endgroup$
    – Kaveh
    Jan 30, 2013 at 16:26
6
$\begingroup$

For a fixed number of tapes greater than one, $\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$) for time-constructible $f$. The logarithmic overhead comes from the tape reduction theorem, where any number of tapes can be converted into two tapes (or even just a single tape and a stack and with just oblivious movement).

If the number of tapes is not fixed, we do not really have a technique to constructively prove $\mathrm{DTime}(g) ⊊ \mathrm{DTime}(f)$ without going through the tape reduction theorem. It is plausible that for every $k$, $k+1$-tape machines cannot be simulated by $k$-tape machines without a logarithmic overhead.

However, that does not mean the time hierarchy theorem cannot be improved, or that $\mathrm{DTime}(o(f)) ⊊ \mathrm{DTime}(O(f))$ fails.

In fact, we already have the following.

Theorem: For every $ε>0$ and every $f$ of the form $n^a (\log n)^b$ ($a$ and $b$ rational; $a>1$ or $a=1∧b≥0$), $\mathrm{DTime}(O(f /(\log f)^ε) ⊊ \mathrm{DTime}(O(f))$.

Proof: If every language with an $O(f)$ decision algorithm can be decided in $O(f / (\log f)^ε)$ time, then by padding the input, every language with an $O(f(n) (\log f(n))^{kε})$ decision algorithm can be decided in $O(f(n) \, (\log f(n))^{(k-1)ε})$ time (where $k≥0$ is fixed), and so for every constant $c≥0$, $\mathrm{DTime}(O(f(n) (\log f(n))^c)) = \mathrm{DTime}(O(f(n)))$, contradicting the time hierarchy theorem.

However, this nonconstructive proof has three limitations:
* The proof requires $f$ to be well-behaved (not only time-constructible, but also in a certain sense continuous).
* We do not know a particular language that is in $\mathrm{DTime}(O(f))$ but not in $\mathrm{DTime}(O(f/(\log f)^ε)$. For a sufficiently large $k$, simulation of $k$-tape Turing machines is not in $\mathrm{DTime}(O(f/(\log f)^ε)$, but we have not ruled out that even for $ε=1$ and $f(n)=n^2$, the least such $k$ is >BB(BB(1000)) where BB is the busy beaver function.
* We do not know that the inclusion is robust. A $\mathrm{DTime}(O(f/(\log f)^ε)$ algorithm will fail for some input, but we have not proved that it fails for some input for all but finitely many input sizes (though it would be very surprising if it did not).

$\endgroup$
1
  • $\begingroup$ Awesome answer!! :) $\endgroup$ Sep 13, 2017 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.