Algorithms For Dummies

 

»

Atlantic City: These algorithms run in polynomial time, providing a correct 

problem answer at least 75 percent of the time. Monte Carlo algorithms are 

always fast but not always correct, and Las Vegas algorithms are always correct 

but not always fast. People therefore think of Atlantic City algorithms as halfway 

between the two because they are usually both fast and correct. This class of 

algorithms was introduced in 1982 by J. Finn in an unpublished manuscript 

entitled Comparison of Probabilistic Test for Primality. Created for theoretical 

reasons to test for prime numbers, this class comprises hard-to-design 

solutions, thus very few of them exist today.