3 ms·
The notion of sublinear time only makes sense with Random-access Machines [1], not with Turing Machines. [1] https://en.wikipedia.org/wiki/Random-access_machin
by tromp 2y ago
The notion of sublinear time only makes sense with Random-access Machines [1], not with Turing Machines.
[1] https://en.wikipedia.org/wiki/Random-access_machine https://en.wikipedia.org/wiki/Random-access_machine
- dooglius 2y agoPretty much any standard notion of time complexity requires one to assume a random access machine, or else e.g. an array access is O(index) time.
- tromp 2y agoTuring machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes like DTIME and NTIME are defined for (single- or multi-tape) Turing machines [1]. [1] https://en.wikipedia.org/wiki/DTIME https://en.wikipedia.org/wiki/DTIME