2
$\begingroup$

$\mathsf{LTIME = DTIME(\log n), NLTIME = NTIME(\log n)}$.

For example, it seems that NTM can find an element in unsorted array in log-time by use of non-deterministic binary search (check if first half leads to solution and if second half leads to solution).

Obviously, it can't be done by log-time deterministically. I couldn't find anything about this despite the fact this is so simple.

So, was it known and does it imply any consequences? (DFA vs NFA, for example).

I also believe it doesn't imply $\mathsf{P \subsetneq NP}$ because $\mathsf{LTIME}$ is smaller class than $\mathsf{P}$ and inequality between bigger classes is stronger statement (maybe it's some kind of any hierarchy rule). Or does it?

Improve this question
$\endgroup$
8
  • $\begingroup$ "NTM can find an element in unsorted array in log-time" - Really? How? Why do you say that? That doesn't sound right to me at all. I've never heard of a complexity class called LTIME or NLTIME, and it doesn't appear in the complexity zoo. How are they defined, precisely? $\endgroup$
    – D.W. ♦
    Jun 24, 2017 at 15:02
  • $\begingroup$ @D.W. Isn't it how deterministic machine works: it can take first half or second half, and choose one that leads to correct solution. Thus, it can use binary search in unsorted array. About complexity classes.. I define them as $\mathsf{DTIME(\log n)}$ and $\mathsf{NTIME(\log n)}$. $\endgroup$
    – rus9384
    Jun 24, 2017 at 15:12
  • $\begingroup$ Please edit the question to include your justification for that statement, so that we can understand your thought process and have something specific to respond to. Don't just put it in the comments -- edit the question to include that information in the body of the question itself. $\endgroup$
    – D.W. ♦
    Jun 24, 2017 at 15:13
  • 2
    $\begingroup$ Turing machines are not random-access. The head moves one position at a time. Your question makes more sense for stronger models such as the random-access machine. $\endgroup$
    – Yuval Filmus
    Jun 25, 2017 at 4:12
  • 1
    $\begingroup$ No. You can accept the language of all strings starting with 0 in constant time. $\endgroup$
    – Yuval Filmus
    Jun 25, 2017 at 13:05

1 Answer 1

Reset to default
5
$\begingroup$

The other answer is quite misleading. The classes $\mathrm{DTIME}(\log n)$ and $\mathrm{NTIME}(\log n)$, usually denoted DLOGTIME and NLOGTIME, do indeed have a sensible and well-accepted meaning in the literature.

When discussing sublinear time classes (deterministic, nondeterministic, alternating, etc.), it is standard to use a Turing machine model that does not have an input tape, but a query tape on which one can write (in binary) the index of an input position, and obtain the input symbol at that position by entering a special state. (The query tape is not cleared or otherwise modified after a query.) This is essentially the same mechanism as used by oracle Turing machines, and the model is sometimes called the random-access Turing machine.

And yes, it is known that $\mathrm{DLOGTIME\subsetneq NLOGTIME}$: a simple NLOGTIME language not recognizable in DLOGTIME is $$L=\{w\in\{0,1\}^*: \text{$w$ has at least one $1$ at some position}\}.$$ There are unconditional separations like this even for some bigger classes, for example $\mathrm{AC^0}$, whose uniform version coincides with languages recognizable by an alternating TM in time $O(\log n)$ with $O(1)$ alternations.

Improve this answer
$\endgroup$

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.