Loading article…
コンピューティングにおいて、アトランティックシティアルゴリズムとは、少なくとも75%の確率で正解するランダム化アルゴリズムである[ 1 ]。いくつかの定義のバリエーションでは、正解の閾値は50%を超える任意の値になる場合がある[ 2 ]。いずれの意味でも、アトランティックシティアルゴリズムはモンテカルロアルゴリズムの一種である。
有界確率的多項式時間問題のクラスBPPに属する任意の問題に対して、多項式時間アトランティックシティアルゴリズムが存在する[ 1 ]。
ラスベガスアルゴリズムは、決して誤った答えを返さないため、モンテカルロアルゴリズムの双対であり、したがってアトランティックシティアルゴリズムの双対でもある。
この名前は、アメリカ合衆国ニュージャージー州のアトランティックシティを指している。モンテカルロやラスベガスと同様に、アトランティックシティはカジノとギャンブル文化で広く知られている。