What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?

Question

According to Wikipedia,

A $\rho$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $\rho$ times the value, $OPT$, of an optimum solution.

I am interested in a situation where we would like to measure the performance of $A$ by how often it finds the optimal solution. For example, the algorithm $A$ finds the optimal value $R$ % of the time and finds a strictly larger (or less) solution $100-R$ % of the time. What would such algorithm be called? Is this notion known in the literature?

Answer 1

The idea you mention is covered in complexity theory by probabilistic classes.

The computational model they refer to is the probabilistic Turing machine, i.e. a Turing machine equipped with an additional read only tape that at the beginning of the computation contains an infinite sequence of symbols, independently chosen at random with uniform probability from the machine alphabet. Or, equivalently, a Turing machine that can flip a fair coin and read the answer in constant time.

Observe that due to the way that our computational model works, two executions on the same instance may give two different answers; for instance, one could define a machine that flips a coin and returns YES on heads and NO on tails.

We are interested in both the asymptotic worst-case running time and the probability that the answer given is actually correct. In literature, a vast amount of different classes are analyzed, they differ depending on various constraints that they impose on the solver.

Perhaps the most interesting of such classes, both from a theoretical and practical point of view is $\mathcal{BPP}$, defined as the class of languages decidable in polynomial time by a probabilistic Turing machine that, whether the answer is YES or NO, is guaranteed to give a correct answer with probability at least $2/3$. Notably, it is an open problem whether or not $\mathcal{P} = \mathcal{BPP}$.

A full discussion of probabilistic complexity theory would be too lengthy for SE, although there are plenty of sources available in both electronic and dead-tree form.