8
$\begingroup$

I noticed that in complexity classes, logspace class is defined but there is no logtime.

I was wondering how is that possible?

Normally, I would expect the opposite, It is possible to do a search query in an ordered list in time less than the time of iterating over all items (==> Logtime?). However you can't store a list in of size n in log(n) space...

So how come Logspace exists but not logtime? there's obviously something wrong with my reasoning.

Could someone please correct me?

Thanks in advance

$\endgroup$
15
$\begingroup$

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting.

What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform circuits. A related complexity class is ALOGTIME, which is the uniform version of NC¹. Buss famously proved that the formula evaluation problem is ALOGTIME-complete. For comparison, the circuit evaluation problem is P-complete.

Algorithms running in $o(n)$ time on random-access machines are known as sublinear time algorithms. Such algorithms also abound in the area of data structures.

$\endgroup$
2
  • 4
    $\begingroup$ Since the question also shows some confusion about logspace, it might be worth mentioning that in the Turing machine model, the "logarithmic space" corresponds to the size of a working tape additionally to the input tape. $\endgroup$ – ttnick Feb 4 at 15:24
  • $\begingroup$ @ttnick, the reason I did not accept this answer immediately was because it lacked the extra information you just mentioned! Now I'm good, I have my answer. Thank you both! $\endgroup$ – user206904 Feb 4 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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