Jump to content

Probabilistic algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 213.253.39.xxx (talk) at 21:39, 10 January 2002. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The terms probabilistic method and probabalistic algorithm are used for methods of approximate calculation based on probability theory, e.g., monte-carlo algorithms, simulated annealing etc.


For example, there exist probabilistic algorithms for proving primality, where the probability of error can be reduced to an arbitary degree by performing enough independent tests.


If, using such a method, the probability of error is 2-1000, the philosophical question arises: is this a proof? After all the probability of error is distinctly smaller than the probability of an error in the reader's computer, or the reader themselves making an error in reading a proof - what does it mean in real terms to consider this small a probability?


Retrieved from "https://en.wikipedia.org/w/index.php?title=Probabilistic_algorithm&oldid=276311"