As we know on NDTM all the possible solutions for a given problem is verified the similar kind of work is done in bogo sort sequentially.

So in future if an NDTM will be there. can we say it will be using bogo sort for sorting?


1 Answer 1


Sure, bogosort is efficient on a nondeterministic Turing machine.

But there is no known way to implement a nondeterministic Turing machine so the answer to any question of the form "If we have a physical nondeterministic, will it do X?$ is the same as "If I become pope, will X happen?" The answer is almost certainly "yes" because false implies anything.


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.