# Can an algorithm be truly non-deterministic?

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.

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

• What is a "non-deterministic algorithm" for you? This term has several different meanings. Please update your question instead of answering in the comments. Commented May 22, 2018 at 18:05

## 1 Answer

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 inefficient 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.