gotchaModerate
why does LSPACE(log space) complexity class exist but not logtime?
Viewed 0 times
whyspaceloglogtimebutlspaceexistdoesclasscomplexity
Problem
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#135088, answer score: 17
Revisions (0)
No revisions yet.