# Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms?

From Wikipedia

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.

a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabalistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.

Are randomized algorithms and probablistic algorithms the same concept?

If yes, so are randomized algorithms just a kind of nondeterministic algorithms?

-
these are different concepts, non deterministic is like pattern of walking of you in one day, and randomize is like a way you choose to go out of maze, in the first sample you don't know how is your walk pattern for today, it's non deterministic and depends to environment changes, in the second sample, your goal is going out of maze, so at first you try some ways then you will find your way, actually in second sample your algorithm is deterministic, means the output is your freedom which is unique in all runs but your startup walks to finding this way are selected by randomize algorithm. – user742 Oct 11 '12 at 5:52
@Saeed You should post this as an answer! – Yuval Filmus Oct 11 '12 at 5:56
@SaeedAmiri: Thanks! (1) I guess it is a good analogy, but I don't understand it. May you try to rephrase it a little? (2) If I understand you correctly, nondeterminsitic algorithm won't always output the correct output, but randomized algorithms will? Is that what you meant by saying randomized algorithms are in fact determinsitic? (3) By "first sample" and "second sample", do you mean nondeterministic algorithms and randomized algorithms respectively? – Tim Oct 11 '12 at 6:37
@Tim, I think Yuval answer is good for your purpose, but note that randomized algorithm can be deterministic or non deterministic. non-deterministic algorithm can be randomize or non randomize, these are different concepts, I think I should explain this in more samples but my current physical situation doesn't let me to type more, I think if you ask Yuval to explain it with more examples you can get it in the right way. – user742 Oct 11 '12 at 7:07
– Gilles Oct 14 '12 at 23:53

Non-deterministic algorithms are very different from probabilistic algorithms.

Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. Probabilistic algorithms are practical, and are used for example by your computer when generating RSA keys (to test that the two factors of your secret key are prime). Probabilistic algorithm which don't use any coin tosses are sometimes called "deterministic".

Non-deterministic algorithms are ones which "need a hint" but are always correct: they cannot be fooled by being given the wrong hint. As an example, here is a non-deterministic algorithm that factors an integer $n$: guess a factorization of $n$, and verify that all the factors are prime (there is a "fast-in-theory" deterministic algorithm for doing that). This algorithm is very fast, and rejects false hints. Most people think that randomized algorithms can't factor integers that quickly. Clearly this model of computation isn't realistic.

Why do we care about non-deterministic algorithms? There is a class of problems, known as NP, which consists of decision problems which have efficient non-deterministic algorithms. Most people think that the hardest problems in that class, the so-called NP-complete problems, do not have efficient deterministic (or even randomized) algorithms; this is known as the P vs NP question. Since many natural problems are NP-complete, it is interesting to know whether in fact they are not solvable efficiently, in the worst case (in practice, oftentimes the instances which arise in practice are in fact solvable in reasonable time).

-
Thanks! (1) I remember NP problems are those that can be solved by an algorithm on a nondeterministic Turing machine in polynomial time. So are "an algorithm on a nondeterministic Turing machine" and "a nondeterministic algorithm on a deterministic Turing machine" equivalent in some sense? (2) Do you think probabalistic algorithm and randomized algorithm are the same concept? (3) Do you also think that Wikipedia says concurrent algorithm and probabalistic algorithm are two kinds of nondeterministic algorithms is wrong? – Tim Oct 11 '12 at 6:32
I don't think the certificate flavor of nondeterminism serves to clarify the difference with randomisation. – Raphael Oct 11 '12 at 7:35
(1) Yes, the two are the same. (2) These are two names for the same concept. (3) Wikipedia is giving some examples of other types of algorithms, though the presentation might be misleading. Parallel and probabilistic algorithms are not non-deterministic. – Yuval Filmus Oct 11 '12 at 12:49
(3) Reading the Wikipedia definition, they visibly meant what Alex wrote in his answer below. – Yuval Filmus Oct 11 '12 at 20:52
@ShelbyMooreIII Non-determinism has a very specific technical meaning in recursion theory and theoretical computer science. – Yuval Filmus Dec 11 '15 at 18:58

An algorithm specifies a method to get from a given input to a desired output that has a certain relation with the input. We say that this algorithm is deterministic if at any point, it is specified exactly and unambiguously what the next step in the algorithm is that must be performed as part of that method, potentially dependent on the input or the partial data computed so far, but always uniquely identified.

Nondeterminism means that some part of the algorithm is left under or even unspecified. For example, "int i = an even number between 0 and n" is underspecified. This means there is no unique behavior that is specified at this point.

For this distinction to be useful, you need the (usual) concept of 'correctness' for (deterministic) algorithms, which informally is that "the algorithm always computes what I want it to compute". It then becomes interesting to think about what correctness would mean for nondeterministic algorithms, which must take into account the choices possible in underspecified instructions.

There are two ways of defining correctness for nondeterminism. The first one is rather simple and less interesting, for which correctness means "the algorithm always computes what I want it to compute, for all sequences of choices I am allowed to make". This sometimes occurs if an author of a bit of pseudocode is too lazy to pick a number and says "pick any even number between 0 and n", when "pick 0" would have made the algorithm deterministic. Essentially, by replacing all nondeterminism by the result of some choice you can make the algorithm deterministic.

This is also the 'nondeterminism' referred to in your second paragraph. This is also the nondeterminism in parallel algorithms: in these algorithms you are not quite sure what execution precisely looks like, but you know that it will always work out, no matter what happens exactly (otherwise your parallel algorithm would be incorrect).

The interesting definition of correctness for nondeterministic algorithm is "the algorithm always computes what I want it to compute, for some sequence of choices I am allowed to make". This means that there may be choices that are wrong, in the sense that they make the algorithm produce the wrong answer or even go in an infinite loop. In the example "pick any even number between 0 and n", perhaps 4 and 16 are right choices, but all other numbers are wrong, and these numbers may vary depending on the input, the partial results and the choices made so far.

When used in computer science, nondeterminism is usually limited to nondeterministically choosing either a 0 or a 1. However, if you pick many such bits nondeterministically, you can generate long nondeterministic numbers or other objects, as well as make nondeterministic choices, so this hardly (if ever) limits its applicability - if applicability is limited, nondeterminism was too powerful in the first place.

Nondeterminism is a tool that is exactly as powerful as a certificate-based deterministic algorithm, that is, an algorithm that checks a property given an instance and a certificate for that property. You can simply nondeterministically guess the certificate for one direction, and you can give a certificate that contains all the 'right' answers for the nondeterministic guesses of 0 and 1 of your program for the other direction.

If we throw running time into the mix, then things become even more interesting. The running time of a nondeterministic algorithm is usually taken to be the minimum over all (right) choices. However, other choices may lead to a dramatically worse running time (which can be asymptotically worse or even arbitrarily worse than the minimum), or even an infinite loop. This is why we take the minimum: we do not care about these weird cases.

Now we get to randomized algorithms. Randomized algorithms are like nondeterministic algorithms, but instead of 'allowing' the choice between 0 and 1 at certain points, this choice is determined by a random coin toss at the time that the choice has to be made (which may differ from run to run, or when the same choice has to be made again later on during the execution of the algorithm). This means that the result is 0 or 1 with equal probability. Correctness now becomes either "the algorithm nearly always computes what I want it to compute" or "the algorithm always computes what I want it to compute" (just the deterministic version). In the second case the time the algorithm needs to compute its answer is usually 'nearly always fast', contrasting with a deterministic 'always fast'.

Contrasting the three: deterministic algorithms exactly specify the answer to the choice, nondeterminism leaves it completely open, but tells you a 'right' answer exists, and randomization leaves the answer up to chance. Note that you can just guess the right coin tosses, which gives rise to a hierarchy between these three: nondeterminism is as powerful as randomization, which in turn is as powerful as determinism, or, with respect to polynomial time, $P \subseteq ZPP \subseteq NP$. In this setting, no proofs are known whether any is strictly more powerful than another.

-
"The running time of a nondeterministic algorithm is usually taken to be the minimum over all (right) choices." -- I thought so, too, but apparently it's wrong. (It would allow $O(|s|)$ algorithms for all problems, where $s$ is the solution, after all.) – Raphael Oct 14 '12 at 10:46

You should be aware that there are two different definitions of nondeterminism being thrown around here.

1. As wikipedia defines it, pretty much "not determinism", that is, any algorithm that doesn't always have the same behavior on the same inputs. Randomized algorithms are a special case of "not deterministic" algorithms, because they fit the definition as I just gave it.

2. Nondeterministic models of computation (like nondeterministic turing machines) are theoretical models of computation. They may have multiple possible paths of execution and they "accept" if any of those paths accept. You should note they aren't real. There is no way to physically run an algorithm that is nondeterministic in this sense, although you can simulate it with a randomized or deterministic one.

In CS, nondeterminism usually means (2), so Wikipedia's definition you gave (which is (1)) is misleading. Most of the answers given so far explain (2), not (1).

-
According to 1), randomised Quicksort is a deterministic algorithm; I'm not sure that is useful terminology. I guess 1) could be described as "black-box" view while 2) actually inspects the algorithm/machine at hand. Arguably, CS is all about 2); I'd assign viewpoint 1) to (modular) software engineering. – Raphael Feb 2 '14 at 17:45
@Raphael, Good point, I should fix (1) to say "have the same behavior on the same inputs". Agreed about preferring (2) over (1). – usul Feb 2 '14 at 18:42
"Behaviour" is ambiguous, exactly in the black- vs white-box way. :) – Raphael Feb 2 '14 at 18:44
Sure, but, I guess I view the important distinction as between a formal, precisely defined nondeterministic Turing Machine (2) and vague/ambiguous "not determinism" (1), which could include randomness (whereas an NTM doesn't). So that's all I wanted to say.... – usul Feb 2 '14 at 18:51
There is nothing 'unreal' about running a nondeterministic algorithm, it just means that while running, choices need to be made for which the outcome isn't determined by the algorithm. The only difference between 1 and 2 is that in 1 you haven't said when the algorithm is considered to "succeed", whereas in 2 the algorithm must be of the kind that always says "yes" or "no" at the end of a run and you have a decision problem and you define the algorithm's answer to the problem as "yes" if and only if any one of its possible runs answers "yes". So 2 is just a special case of 1. – reinierpost Dec 11 '15 at 23:25

In short: non-determinism means to have multiple, equally valid choices of how to continue a computation. Randomisation means to use an external source of (random) bits to guide computation.

In order to understand nondeterminism, I suggest you look at finite automata (FA). For a deterministic FA (DFA), the transition function is, well, a function. Given the current state and the next input symbol, the next state is uniquely defined.

A non-deterministic automaton (NFA), on the other hand, has a transition relation: given the current state and the next input symbol, there are multiple possible next states! For example, consider this automaton for the language $(ab)^*(ac)^*$:

[source]

The automaton guesses which $a$ marks the border between $(ab)^*$ and $(ac)^*$; a deterministic automaton would have to postpone its decision until after having read the symbol after each $a$.

The key point here is that acceptance is defined as "accept if there is an accepting run" for NFA. This existence criterion can be interpreted as "always guessing right", even though there is no actual guessing.

Note that there are no probabilities here, anywhere. If you were to translate nondeterminism into programming languages, you would have statements that can cause jumps to different other statements given the same state. Such a thing does not exist, except maybe in esoteric programming languages designed to skrew your mind.

Randomisation is quite different. If we break it down, the automaton/program does not have multiple choices for continuing execution. Once the random bit(s) are drawn, the next statement is uniquely defined:

if ( rand() > 5 )
do_stuff();
else
do_other_stuff();


In terms of finite automata, consider this:

[source]

Now every word has a probability, and the automaton defines a probability distribution over $\{a,b,c\}^*$ (differences between $1$ and the sum of outgoing edges is the probability of terminating; words that can not be accepted have probability $0$).

We can view this as a deterministic automaton, given the sequence of random decisions (which models practice quite well, as we usually use no real random sources); this can be modelled as a DFA over $\Sigma \times \Pi$ where $\Pi$ is a sufficiently large alphabet used by the random source.

One final note: we can see that nondeterminism is a purely theoretical concept, it can not be implemented! So why do we use it?

1. It often allows for smaller representations. You might know that there are NFA for which the smallest DFA is exponentially as large¹. Using the smaller ones is just a matter of simplifying automaton design and technical proofs.

2. Translation between models is often more straight-forward if nondeterminism is allowed in the target model. Consider, for instance, converting regular expressions to DFA: the usual (and simple) way is to translate it to an NFA and determinise this one. I am not aware of a direct construction.

3. This may be an academic concern, but it is interesting that nondeterminism can increase the power of a device. This is not the case for finite automata and Turing machines, arguable the most popular machine models devices, but for example deterministic pushdown-automata, Büchi automata and top-down tree automata can accept strictly less languages than their non-deterministic siblings².

1. See this question on cstheory.SE for an example.
2. See here, here and here (Proposition 1.6.2), respectively.
-

Randomized (polynomial time, boolean result) algorithms are in the RP computational complexity class, which is a subset of NP where non-deterministic (polynomial time, boolean result) algorithms reside and a superset of P where deterministic (polynomial time, boolean result) algorithms reside.

Subsetting complexity is about reducing problems in one set to another set. Thus RP ⊆ NP does exclude the possibility of randomized algorithms which are also non-deterministic because definitionally a superset contains the subset. Subset means every RP algorithm (or any RP-complete algorithm) can be reduced to some NP algorithm (or any NP-complete algorithm). P is a subset of RP because every problem in P can be reduced to a problem in RP where the amount of uncontrolled entropy is 0.

Tangentially, this is analogous to how every problem in NC (parallel computation) can be reduced to a problem in P by simulating the parallel computation in a reduction to a serial problem in P but it is not yet proven that the converse is true, i.e. that every problem in P is reducible to a problem in NC, nor proven not true, i.e. the implausible proof that a P-complete problem is not reducible to a problem in NC. It may be possible that there are problems that are inherently serial and can't be computed in parallel, but to prove that prove P ≠ NC seems to be implausible (for reasons too tangential to discuss in this answer).

More generally (i.e. not limited to boolean result types), randomized algorithms are distinguished from deterministic algorithms in that some of the entropy is externally sourced. Randomized algorithms are distinguished from non-deterministic algorithms because the entropy is bounded, and thus randomized (and not non-deterministic) algorithms can be proven to always terminate.

The unpredictability of nondeterministic algorithms is due to inability to enumerate all the possible permutations of the input entropy (which results in unpredictability of termination). The unpredictability of a randomized algorithm is due to inability to control all of the input entropy (which results in a unpredictability of an indeterminate result, although the rate of unpredictability can be predicted). Neither of these are statements about unpredictability of the correct answer to the problem, but rather the unpredictability manifests in the side-channel of termination and indeterminate result respectively. It seems many readers are conflating unpredictability in one area with unpredictability of the correct result, which is a conflation I never wrote (review the edit history).

It is key to understand that non-determinism is always (in any science or usage of the term) the inability to enumerate universal (i.e. unbounded) entropy. Whereas, randomization refers to accessing another source of entropy (in programs entropy other than and thus not under the control of the input variables) which may or may not be unbounded.

All sciences use the same definition of nondeterminism unified on the concept of unbounded entropy. Unpredictable outcomes in all sciences are due to the inability to enumerate a priori all possible outputs of an algorithm (or system) because it accepts unbounded states, i.e. NP complexity class. Specifying a particular input to observe whether it halts and noting that the result is idempotent is equivalent in other sciences to holding the rest of the entropy of the universe constant while repeating the same state change. Computing allows this entropy isolation, while natural sciences don't.

It is really quite elegant and easy to see the distinction, once you all stop muddling it by trying to describe it from an operational point-of-view instead of from the salient entropy point-of-view.

@reinierpost everyone is conflating the difference between randomized and nondeterministic. This causes your comment to be muddled. The algorithm responds to the interaction of the input (variable) entropy and its source code (invariant) internal entropy. Nondeterminism is unbounded entropy. Invariant entropy can even be internally unbounded such as expanding the digits of π. Randomized is some of the entropy is not coupled to the input as defined (i.e. it may be coming from a system call to /dev/random, or simulated randomness e.g. NFA or a PRNG).

.

@Raphael formal definition of non-deterministic finite automa (NFA) is finite input entropy (data: the 5-tuple). Thus every NFA can run on a deterministic Turing machine, i.e. doesn't require a nondeterministic Turing-complete machine. Thus NFAs are not in the class of nondeterministic problems. The notion of "nondeterminism" in NFA is that its determinism (while clearly present since every NFA can be converted to a DFA) is not explicitly expanded — not the same as nondeterminism of computation

.

@Raphael the claimed "non-determinism" in NFAs is really randomness is sense of my definition of the distinction between randomness & nondeterminism. My definition is that randomness is where some of the entropy that is not under the control, knowledge (, or desired non-explicit expansion in the case of a NFA) of the input to the program or function. Whereas, true nondeterminism is the inability to know the entropy in any case, because it is unbounded. This is precisely what distinguished randomized from nondeterminism. So NFA should be an example of the former, not the latter as you claimed.

.

@Raphael as I explained already, the notion of non-determinism in NFAs couple the non-deterministic with the finite entropy. Thus the non-determinism is a local concept of not expanding the determinism as a form of compression or convenience, thus we don't say NFAs are non-deterministic, rather they possess appearance of randomness to an oracle unwilling to compute the deterministic expansion. But it is all a mirage because it call be expanded deterministically bcz the entropy is not unbounded, i.e. finite.

Dictionaries are tools. Learn to use them.

Statistics. of or characterizing a process of selection in which each item of a set has an equal probability of being chosen.

being or relating to a set or to an element of a set each of whose elements has equal probability of occurrence

Thus randomization only requires that some of the input entropy be equiprobable, which is thus congruent with my definition that some of the input entropy not be controlled by the caller of the function. Notice that randomization does not require that the input entropy be undecidable w.r.t. to termination.

In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.

Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.

Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.

So this is telling us that deterministic algorithms must be completely determined by the input state of the function, i.e. we must be able to prove that the function will terminate (or not terminate) and that can't be undecidable. In spite of Wikipedia's muddled attempt to describe nondeterministic, the only antithesis to deterministic as defined above by Wikipedia, is are algorithms whose input state (entropy) is ill-defined. And the only way the input state can be ill-defined is when it is unbounded (thus can't be deterministically preanalyzed). This is precisely what distinguishes a nondeterministic Turing machine (and many real world programs which are written in common Turing complete languages such as C, Java, Javascript, ML, etc..) from deterministic TMs and programming languages such as HTML, spreadsheet formulas, Coq, Epigram, etc.. Wikipedia sort of alludes to this:

In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a man walking down a path in a forest and, every time he steps further, he must pick which fork in the road he wishes to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the man walking through the forest may only find his cabin if he picks some combination of "correct" paths). The choices can be interpreted as guesses in a search process.

Wikipedia and others try to conflate randomization with nondeterminism, but what is the point of having the two concepts if you are going to not distinguish them eloquently?

Clearly determinism is about the ability to determine. Clearly randomization is about making some of the entropy equiprobable.

Including random entropy in the state of an algorithm doesn't necessary make it indeterminable. For example a PRNG can have the required equiprobable statistical distribution, yet also be entirely deterministic.

Conflating orthogonal concepts is what low IQ people. I expect better than that from this community!

-
That isn't what nondeterminism means in computer science. Nondeterministic algorithms are not "unpredictable." – David Richerby Dec 11 '15 at 22:50
I answer has nothing to with how non-determinism is defined in automata resp. computability theory. Shelby, you should stop flaming around and get a textbook. If you don't understand the other answers, I don't think we can help you in a comment. – Raphael Dec 11 '15 at 23:18
@ShelbyMooreIII You have completely misunderstood what nondeterminism means in computer science. It has nothing whatsoever to do with entropy. It does not mean what you think it means: that is why you think all the other answers are wrong. Perhaps the name was badly chosen but that's beside the point. It has a particular meaning in computer science, which is different from the meaning it has in other sciences. You are trying to use the wrong definition, and that is why everything seems completely wrong to you. – David Richerby Dec 11 '15 at 23:53
"The use of the term nondeterminism when talking about computational complexity theory [...] is clearly all about the entropy" -- no, it's not. – Raphael Dec 12 '15 at 10:12
We can agree on that: please stop trying to "teach" us, it's not helping anybody. – Raphael Dec 12 '15 at 15:17