3 ms·
Often for problems taking integer input x, formal CS will define the input to be something like 1^x (the character '1' repeated x times, as opposed to binary) s
by dooglius 2y ago
Often for problems taking integer input x, formal CS will define the input to be something like 1^x (the character '1' repeated x times, as opposed to binary) so that the time complexity is in terms of x. This class of problems seems amenable to sublinear time since only only needs log(x) steps to determine x.
- LPisGood 2y agoActually if you try to formally define sublinear time algorithms in this manner they all collapse to constant time algorithms. To see why, realize that to determine x, the TM needs to look at x many bits. If this algorithm only needed, say, log(x) many bits to produce output then all input values with more than log(x) bits are indistinguishable by this TM.
- tromp 2y agoThe 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