Linear search is solvable in O(n) time by a deterministic Turing machine. If we apply a nondeterministic Turing machine to the problem, can we solve the decision problem "Is $x$ in the array $A$?" in O(log n) time or even O(1) time? If my understanding of nondeterminism is correct then the answer is yes because it can follow multiple computation paths at once? I.e. the "genie" would just tell the algorithm where the element we are searching for is to be found?

  • $\begingroup$ Clarified that the linear search is a DP. $\endgroup$ Commented Apr 8, 2022 at 9:47

1 Answer 1


No. A Turing machine still needs to move the tape head to each element in the array, by moving one symbol per step, so O(N) movements on average. If the elements each occupy 1 space on the tape, and the 5th element is the one being searched for, the shortest path to an accept state still requires a minimum of 5 steps (to move right 4 times and then check the symbol under the tape head).

If we use some kind of nondeterministic random-access machine instead, where the machine can jump instantly to any element, then it can be done in fewer than O(N) steps, probably O(log N) if not O(1). This would depend on the particular type of machine used.

  • $\begingroup$ This answer the question for my example. But does it hold in general that a NTM can't solve a P-time problem faster than a DTM? $\endgroup$ Commented Apr 8, 2022 at 11:04
  • $\begingroup$ @BjörnLindqvist I can't think of one OTOH, but there are presumably problems where you are searching through values (instead of array elements) to find an "interesting one" and nondeterminism can convert O(N) into O(log N) to branch to all the possible values at once, so instead of e.g. O(N^3) you could have O(N^2 logN) $\endgroup$ Commented Apr 8, 2022 at 11:53
  • $\begingroup$ Does this mean that looking up an array element in a DTM is an O(n) operation? Then, in fact, a DTM is "slower" than a normal computer? $\endgroup$ Commented Apr 8, 2022 at 14:36
  • $\begingroup$ @BjörnLindqvist I believe so. O(n) is still polynomial though, so everything that's polynomial time on a random access machine is also polynomial time on a Turing machine. $\endgroup$ Commented Apr 8, 2022 at 14:41
  • 2
    $\begingroup$ @BjörnLindqvist, basically, yes, but it's a little tricky. It doesn't work with the standard RAM model, but if you use the transdichotomous model, I believe it does. If you want to know more, please ask a new question using the 'Ask Question' button -- this comment thread isn't the place for that. $\endgroup$
    – D.W.
    Commented Apr 8, 2022 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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