Randomized algorithm: Difference between revisions

Revision as of 14:01, 24 November 2018

Revision as of 10:31, 24 December 2018

Line 64:

==Computational complexity==<!-- [[Probabilistic complexity]] and [[Probabilistic computational complexity]] redirect here -->

[[Computational complexity theory]] models randomized algorithms as ''[[probabilistic Turing machine|probabilistic]] [[Turing machinemachines]]s''. Both [[Las Vegas algorithm|Las Vegas]] and [[Monte Carlo algorithm]]s are considered, and several [[complexity class]]es are studied. The most basic randomized complexity class is [[RP (complexity)|RP]], which is the class of [[decision problem]]s for which there is an efficient (polynomial time) randomized algorithm (or probabilistic Turing machine) which recognizes NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class for RP is co-RP. Problem classes having (possibly nonterminating) algorithms with [[polynomial time]] average case running time whose output is always correct are said to be in [[ZPP (complexity)|ZPP]].

The class of problems for which both YES and NO-instances are allowed to be identified with some error is called [[Bounded-error probabilistic polynomial|BPP]]. This class acts as the randomized equivalent of [[P (complexity)|P]], i.e. BPP represents the class of efficient randomized algorithms.