Depending on whether or not they always produce a correct result, algorithms with this property are classified as Las Vegas or Monte Carlo.
This property is exploited immediately prior to the edge-contraction phase of Karger's min-cut algorithm. Every problem in NP has a proof that is checkable by an algorithm with this property, according to the PCP theorem. By the Martin-Löf definition, a sequence has this property if no constructive martingale succeeds on it, or if all its prefixes are Kolmogorov-incompressible. A runtime of "big-O of n log n" is achievable even for worst-case inputs when quicksort is modified to run with this property. Depending on whether or not they always produce a correct result, algorithms with this property are classified as Las Vegas or Monte Carlo. For 10 points, identify this property desirable in cryptographic applications, which is informally equivalent to unpredictability.
This property is exploited immediately prior to the edge-contraction phase of Karger's min-cut algorithm.
randomness [or word forms; or randomized algorithms]