Editing Las Vegas algorithm (section)

== Definition ==
This section provides the conditions that characterize an algorithm's being of Las Vegas type.

An algorithm A is a Las Vegas algorithm for problem class X, if<ref>H.H. Hoos and T. Stützle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.</ref>

#whenever for a given problem instance x∈X it returns a solution s, s is guaranteed to be a valid solution of x
#on each given instance x, the run-time of A is a random variable RT<sub>A,x</sub>

There are three notions of ''completeness'' for Las Vegas algorithms:

* ''complete Las Vegas algorithms'' can be guaranteed to solve each solvable problem within run-time t<small>max,</small> where t<small>max</small> is an instance-dependent constant.

Let P(RT<sub>A,x</sub> ≤ t) denote the probability that A finds a solution for a soluble instance x in time within t, then A is complete exactly if for each x there exists

some t<small>max</small> such that  P(RT<sub>A,x</sub> ≤ t<sub>max</sub>) = 1.

* ''approximately complete Las Vegas algorithms'' solve each problem with a probability converging to 1 as the run-time approaches infinity. Thus, A is approximately complete, if for each instance x, lim<sub>t→∞</sub> P(RT<sub>A,x</sub> ≤ t)  = 1.
* ''essentially incomplete Las Vegas algorithms'' are Las Vegas algorithms that are not approximately complete.

Approximate completeness is primarily of theoretical interest, as the time limits for finding solutions are usually too large to be of practical use.

=== Application scenarios ===
Las Vegas algorithms have different criteria for the evaluation based on the problem setting. These criteria are divided into three categories with different time limits since Las Vegas algorithms do not have set time complexity. Here are some possible application scenarios:

* Type 1: There are no time limits, which means the algorithm runs until it finds the solution.
* Type 2: There is a time limit t<sub>max</sub> for finding the outcome.
* Type 3: The utility of a solution is determined by the time required to find the solution.

(Type 1 and Type 2 are special cases of Type 3.)

For Type 1 where there is no time limit, the average run-time can represent the run-time behavior. This is not the same case for Type 2.

Here, ''P''(''RT'' ≤ ''t<sub>max</sub>''), which is the probability of finding a solution within time, describes its run-time behavior.

In case of Type 3, its run-time behavior can only be represented by the run-time distribution function ''rtd'': ''R'' → [0,1] defined as ''rtd''(''t'') = ''P''(''RT'' ≤ ''t'') or its approximation.

The run-time distribution (RTD) is the distinctive way to describe the run-time behavior of a Las Vegas algorithm.

With this data, we can easily get other criteria such as the mean run-time, standard deviation, median, percentiles, or success probabilities ''P''(''RT'' ≤ ''t'') for arbitrary time-limits ''t''.