2
$\begingroup$

I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the output of the randomness source is considered an input, the algorithm reduces to a deterministic algorithm. So the only non-deterministic algorithm possible is one that produces truly random numbers with no input or the same input. I have read that this is not possible.

Refer: Can a computer generate a truly random number?

So why are certain algorithms called "non-deterministic algorithms"?

$\endgroup$
  • 1
    $\begingroup$ What is a "non-deterministic algorithm" for you? This term has several different meanings. Please update your question instead of answering in the comments. $\endgroup$ – Yuval Filmus May 22 '18 at 18:05
5
$\begingroup$

There are two meanings of non-deterministic.

Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the algorithm can branch into multiple execution paths, and the algorithm accepts if any of these paths accepts. Or, equivalently, you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess. Such an algorithm can't actually be implemented in practice (except by simulating it in an efficient way), so it is more of a thought experiment.

Meaning #2: non-deterministic means "it is not a deterministic algorithm". For instance, such an algorithm might be randomized.

An algorithm that uses random numbers would be considered non-deterministic in the sense of Meaning #2 but not in the sense of Meaning #1.

Usually when you see the phrase "nondeterminism" in complexity theory or algorithms, it will typically mean the former meaning, but no guarantees. You might have to infer which was meant from context.

See also Differences and relationships between randomized and nondeterministic algorithms?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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