「モンテカルロ法」の版間の差分

[[計算理論]]の分野において、モンテカルロ法とは[[多項式時間]]で処理が終了されることは保証されるが、導かれる答えが必ずしも正しいとは限らない[[乱択アルゴリズム]]（ランダム・アルゴリズム）と一般に定義される{{要出典|date=2011年2月}}<ref>http://xw2k.nist.gov/dads/HTML/monteCarlo.html</ref>。一例として[[素数判定|素数判定問題]]における[[ミラー-ラビン素数判定法]]がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。