Randomized algorithm: Difference between revisions

Revision as of 09:46, 17 July 2019

Revision as of 20:54, 25 August 2019

Line 64:

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

[[Computational complexity theory]] models randomized algorithms as ''[[probabilistic Turing machine|probabilistic Turing machines]]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.

Line 99:

Recall that the [[Edge contraction|contraction]] of two nodes, ''u'' and ''v'', in a (multi-)graph yields a new node ''u'' ' with edges that are the union of the edges incident on either ''u'' or ''v'', except from any edge(s) connecting ''u'' and ''v''. Figure 1 gives an example of contraction of vertex ''A'' and ''B''.

After contraction, the resulting graph may have parallel edges, but contains no self loops.

[[File:Single run of Karger’s Mincut algorithm.svg|thumb|340px|Figure 2: Successful run of Karger’sKarger's algorithm on a 10-vertex graph. The minimum cut has size 3 and is indicated by the vertex colours.]]

[[File:Contraction vertices.jpg|300px|thumb|center|Figure 1: Contraction of vertex A and B]]

Karger's<ref>A. A. Tsay, W. S. Lovejoy, David R. Karger, ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.215.794&rep=rep1&type=pdf Random Sampling in Cut, Flow, and Network Design Problems]'', Mathematics of Operations Research, 24(2):383–413, 1999.</ref> basic algorithm: