「ノート:モンテカルロ法」の版間の差分
削除された内容 追加された内容
m 復元 |
|||
30行目:
分かりにくくて済みません．でも，「多項式時間で終了しても完全に答えが出る保証はなく、NP や P に属するかはそんなに明らかでなかったり」という下りで納得しました．確かに「アルゴリズム」は有限時間内に正しい答えを出す，というのが原則的な定義だということに縛られていたので，私の勘違いが発生したようです．どう修正すれば良いかじっくり考えてから提案します．もしかしたらこのままが結果として良いという結論になるかもしれませんが...それと，クラスNでは無く，クラスPでした．失礼しました．
--[[利用者:Kalab1998|Kalab1998]] 2011年2月2日 (水) 01:46 (UTC)
:こんにちわ、一年以上ほったらかしの執筆者です。要出典の部分ですが、一応[[アメリカ国立標準技術研究所|NIST]]の定義を貼り付けてみました。
:ご指摘の点ですが、既に上で述べられているとおりですが計算理論におけるモンテカルロ法の保証は「終了すること」であって「答えが出る」では無いです。極論すれば[[決定問題]]において問題を一切見ずにランダムに答えても確立1/2のモンテカルロ法になります。このモンテカルロ法の内、誤答する確率が1/2未満の定数に収まるのが[[BPP (計算複雑性理論)|BPP]]、1/2まで許容するのが[[PP (計算複雑性理論)|PP]]で、この分野ではほぼ P=BPP、P≠PP（暗に BPP ⊂ NPも）と信じられていますが、確証はいまだに見つかっていなかったはずです。さらにNP ⊂ PPなので、そもそも「NPの難しさとは何か」という考察は、この方面では結構興味深いことになっています。
:記事の修正に関しては特に異論は無いです（むしろ僕の拙文を書き直してくれるなら大歓迎）。 --[[利用者:U-ichi|U-ichi]] 2011年2月21日 (月) 11:28 (UTC)
| |||