Uzasadnienie logarytmu f w twierdzeniu o hierarchii DTIME

30

Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną:

DTIME(flogf)DTIME(f)

Nie mamy tego rodzaju kosztów ogólnych dla NTIME DSPACE. Podstawowe uzasadnienie wynika ze szczegółów dowodu, biorąc pod uwagę różnicę między symulatorami.

Moje pytanie jest następujące: bez uwzględnienia szczegółów dowodu na temat twierdzenia o hierarchii DTIME, czy istnieje uzasadnienie tego logu, czy może to być tylko konsekwencja dowodu i rozsądne byłoby wyobrazić sobie, że gdyby f=o(g) następnie

DTIME(f)DTIME(g)

Moim zdaniem, biorąc pod uwagę, że wyjaśnienie symulacji jest dobrym uzasadnieniem, powinno być samo w sobie uzasadnione przez udowodnienie, że gdybyśmy mieli lepszy wynik, moglibyśmy stworzyć lepszą symulację.

Ludovic Patey
źródło
5
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.
Tsuyoshi Ito
As far as I understand, reducing the Ω(logn) simulation overhead in the deterministic time hierarchy theorem would be a breakthrough result. For one thing, several results could be immediately strengthened.
András Salamon
4
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.
Abel Molina
1
@abel I assume of course that f and g are time-constructible, like in current time hierarchy theorem.
Ludovic Patey
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)
vzn

Odpowiedzi:

5

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 {0k1k|k0} .

On a single tape machine, there is an O(nlogn) 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)logT(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(nlogn). Therefore, A is regular , which is a contradiction. So, we conclude that an overhead of logT(n) is the best we can do when simulating multi tape machines with single tape machines.

Zdaję sobie sprawę, że to mocne stwierdzenie, więc mogę się mylić w mojej interpretacji.

NTIME or SPACE. My intuition derives by the following fact:

There is a very known result that states DTIME(n)NTIME(n). Under the assumption that PNP I believe this result is improved to DTIME(nk)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.

chazisop
źródło
9
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 Ω(n2) on single-tape machines
Luca Trevisan
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(nlogn) 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.
chazisop
The example Luca mentions is for a case where time is o(n2). 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 Ω(n2). Interestingly the proof of the strong version of the hierarchy theorem for o(n2) doesn't use simulation but a direct argument (see Hartmanis 1968).
Kaveh
8

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 Ω(n2) and 2. running-time being o(n2).

  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(n2) 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
Kaveh
źródło
4
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 DTIMEk(f), k being the number of tapes.
Markus Bläser
@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.
Kaveh
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.
Kaveh
5

For a fixed number of tapes greater than one, Time(o(f))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 DTime(g)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 DTime(o(f))DTime(O(f)) fails.

In fact, we already have the following.

Theorem: For every ε>0 and every f of the form na(logn)b (a and b rational; a>1 or a=1b0), DTime(O(f/(logf)ε)DTime(O(f)).

Proof: If every language with an O(f) decision algorithm can be decided in O(f/(logf)ε) time, then by padding the input, every language with an O(f(n)(logf(n))kε) decision algorithm can be decided in O(f(n)(logf(n))(k1)ε) time (where k0 is fixed), and so for every constant c0, DTime(O(f(n)(logf(n))c))=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 DTime(O(f)) but not in DTime(O(f/(logf)ε). For a sufficiently large k, simulation of k-tape Turing machines is not in DTime(O(f/(logf)ε), but we have not ruled out that even for ε=1 and f(n)=n2, 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 DTime(O(f/(logf)ε) 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).

Dmytro Taranovsky
źródło
Awesome answer!! :)
Michael Wehar