Differences and relationships between randomized and nondeterministic algorithms?

Question

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 probabilistic 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 probabilistic algorithms the same concept?

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

Answer 1

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 (oftentimes, the instances which arise in practice are in fact solvable in reasonable time).

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

Revisiting this due to some related research I am doing, the disagreement between myself and some of the others who answered, can be assimilated into a holistic understanding in which we were all correct. But IMO the adopted computer science terminology “bounded nondeterminism” is an incorrect oxymoron (which was my point before).

They key point is to distinguish between bounded and unbounded nondeterminism.[1]

Nondeterministic Turing machines (aka “NTMs”) have bounded nondeterminism in that each state transition has a bounded number of possibilities, i.e. the number of programs (aka “configurations”) is finite. The tape remains unbounded, so the proof of termination remains undecidable. But for any given input that halts, the output is deterministic and bounded in time― i.e. for any input the result is deterministic or doesn’t terminate. Also NTMs execute all possible configurations in parallel, so they execute exponentially faster than emulation of NTMs on deterministic Turing machines (aka “DTMs”).[2]

There really isn’t any nondeterministic relationship between inputs and outcomes in NTMs because the outcome is always the same for any input or initial state, which is evident because they they can be emulated by DTMs without any added randomness.[2] Undecidable is not the antithesis of deterministic, because not halting is also a deterministic result. Deterministic machines always have the same outcome for a given input, even when that outcome is to not halt. The localized nondeterminism of NTMs is in each state transition of the executing algorithm. It is undecidable a priori which path of the tree might terminate providing the output state. But undecidability is not nondeterminism. Thus the term “bounded nondeterminism” is intended to describe the localized indeterminacy within the state machine but not the relationship of inputs to results, hence the concept of “bounded”. I still think the term “bounded nondeterminism” is an oxymoron and it could have been more accurately described as a “parallelized state transition” Turing machine.

Whereas, for any given input or initial state, unbounded nondeterminism (aka “indeterminism”) has an unbounded number of possible states. Unbounded nondeterminism involves not just the number of possible configurations of programs, but some unbounded external state which is not part of the input or initial state, such as unbounded delays. And thus outcomes can vary on repeated executions for the same input or initial condition; thus is not a deterministic relationship between inputs and outcomes.[3]

Randomized and probabilistic algorithms employ some nondeterminism, i.e. random selection of possible configurations possibly bounded in number of configurations, but they don’t execute all the possible configurations as NTMs do. Thus they are not deterministic unless the randomness is deterministic (e.g. PRNG) and the initial state of the entropy for the randomness is considered to be part of the input.

[1] https://en.wikipedia.org/w/index.php?title=Unbounded_nondeterminism&oldid=710628370#Nondeterministic_automata

[2] https://en.wikipedia.org/w/index.php?title=Non-deterministic_Turing_machine&oldid=754212081#Equivalence_with_DTMs

[3] Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know...). Jump to the 17:44 minute mark.

Answer 6

Apart from all the answers which explain the difference, I have an example which may help you get the thing they want to say.
Consider a coin toss, you either get a H or a T. If the coin toss is random, it is highly likely that out of 1000 coin tosses, 500 would be H and it is quite unlikely that 999 out of them would be H. But if the coin toss is non-deterministic, we can't say that getting 999 H would be highly unlikely.