patternMajor
Differences and relationships between randomized and nondeterministic algorithms?
Viewed 0 times
randomizedalgorithmsdifferencesbetweennondeterministicandrelationships
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#5008, answer score: 26
Revisions (0)
No revisions yet.