ノート:モンテカルロ法

真性乱数を生成するICはコンピュータで使われますので、この節分けは不適当かと。kaz 2005年12月5日 (月) 14:33 (UTC)

計算化学や，計算物理のところからリンクされているのにマルコフチェーンモンテカルロ法に関する記述が現在の項目にまったくないのはひどいと思うのですが，どの段階の記述を復活させればいいのでしょう？--以上の署名のないコメントは、121.110.56.75（会話）さんが 2008年6月26日 (木) 14:59 (UTC) に投稿したものです（白駒による付記）。

計算理論上の矛盾

計算理論の項目中に「モンテカルロ法とは多項式時間で処理が終了されることは保証されるが、」とあるが，計算複雑性理論としてはBPPとNPの関係が分かっていないとしています．これは一見、矛盾した説明になっていて，もう少し噛み砕いた説明が必要に思われますがいかがでしょうか？

また、モンテカルロ法に置ける多項式時間は何に対してnと置くのでしょうか？例えば整列の場合，列の長さがnになり，nが大きくなれば問題も難しくなるといえます．しかし，モンテカルロ法で矢の数をnと置いて、nの数を増やしても問題の難しさが変わるわけではなく，単に答えに近づくだけです．そういう意味で私はモンテカルロ法はO(1)と考えていました．私の考えは間違っているのでしょうか？

もう少し考えて見ました．モンテカルロ法で，ある乱数値を決定し，この乱数値が解空間に所属しているかどうかを調べる関数があるとします．この関数の実行時間が乱数値の大小によって指数関数的に実行時間が増大するような関数の場合でも多項式時間内で終了すると言えるのでしょうか?

上記は非現実的な設定かもしれませんが，逆に解空間に存在するかどうかを判定する関数は乱数値によらず定数時間で解決するだろうと予想します．そうすると，モンテカルロ法は定数時間で終了する，あるいは少なくとも矢の数nに線形比例した時間で終了することになり，多項式時間よりも小さい時間で済むことになります．やはり，何を根拠に多項式時間と述べているのか私には分かりません．

--Kalab1998 2011年1月29日 (土) 15:23 (UTC)

文脈から、例としてミラー-ラビン素数判定法が念頭にあるようです。素数かどうか知りたい自然数 n が大きくなると、同じ矢の数でも n を法とする法計算に時間がかかるようになるが、それは (n のビット数の) 多項式オーダーだ、と。データのサイズに依らないアルゴリズムだとしても、1 も多項式のひとつなので、別に矛盾はないように思います（誤解しそうなら、「高々」多項式時間、と書けばどうか）。私は計算理論のことはほとんど何も知りませんし、当該部分を執筆した方は継続的に活動されていますので、その方の返事を待つのが良いとは思いますが、確かにモンテカルロ法の定義あるいは説明としてこのようなものは（私は）見かけませんので、出典を求めるタグ（Template:要出典）等を貼るなどされてはいかがか、と思います。--白駒 2011年1月30日 (日) 00:37 (UTC)

◆失礼しました。執筆した方は活動を停止されていますね。日付を一年見間違えておりました。 ミラー・ラビンをモンテカルロ法の一種と見なすのがスタンダードなのか等、私には分かりませんので、要出典タグを付けておきました。--白駒 2011年1月31日 (月) 22:55 (UTC)

要出典タグを付けていただき有り難うございます．一応ここで議論が成立したら表のページの何らかの編集をと考えていました．「計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。」という記述がある訳ですが，その後で「現在、NP ⊂ PP 、RP ⊆ NPであることは解っているが BPP と NPとの関係は解っていない。」と述べています．これはモンテカルロ法が本質的な所でクラスNを保証していないと考えています．クラスNが保証されていないのに多項式時間の実行完了が保証されるという部分に矛盾を感じています．どこかに数学的な証明があれば良いのでしょうが，私もツールとして使う立場なので，あんまり深くは突っ込めないでいます．

反例として１つ挙げると，ある面積を求める問題で精度(有効桁数)をnと置いたとき，矢の数は指数関数的に増大することになり，当然実行時間も指数関数的に増大します．これは問題設定が誤りなんでしょうか?

--Kalab1998 2011年2月1日 (火) 13:59 (UTC)

ちょっと話に付いていけないですが…。多項式時間というのは、入力サイズに対しての用語だと私は理解していますので、精度の桁数に対して指数時間だ、という指摘は無意味に思えます。「モンテカルロ法が本質的な所でクラスN (NP のことか？) を保証していないから矛盾」の意味はちょっと分かりません。NP に属するかどうかわからないということと、正しい答えが出る保証はないが多項式時間で終了するということは、何の矛盾もないように思います。例えば、素数判定の問題はミラー・ラビンによって BPP に属するわけですが、ミラー・ラビンは多項式時間で終了しても完全に答えが出る保証はなく、NP や P に属するかはそんなに明らかでなかったりします (実際はAKS素数判定法によって P に属する)。

いろいろと齟齬が生じるのは、執筆者と Kalab1998 さんのバックグラウンドが異なるからではないか、という気がします。モンテカルロ法という用語は、元々数値積分に由来する、ということは複数の文献から確かめられると思いますから、そういう説明を前面に押し出すことには反対致しませんし、問題の部分は出典が付かなければ除去もやむを得ないとは思います。--白駒 2011年2月1日 (火) 18:52 (UTC) 「噛み砕いた説明が必要」という意図が分かったように思いますので、一部撤回します。--白駒 2011年2月1日 (火) 19:38 (UTC)

分かりにくくて済みません．でも，「多項式時間で終了しても完全に答えが出る保証はなく、NP や P に属するかはそんなに明らかでなかったり」という下りで納得しました．確かに「アルゴリズム」は有限時間内に正しい答えを出す，というのが原則的な定義だということに縛られていたので，私の勘違いが発生したようです．どう修正すれば良いかじっくり考えてから提案します．もしかしたらこのままが結果として良いという結論になるかもしれませんが...それと，クラスNでは無く，クラスPでした．失礼しました． --Kalab1998 2011年2月2日 (水) 01:46 (UTC)

こんにちわ、一年以上ほったらかしの執筆者です。要出典の部分ですが、一応NISTの定義を貼り付けてみました。

ご指摘の点ですが、既に上で述べられているとおりですが計算理論におけるモンテカルロ法の保証は「終了すること」であって「答えが出る」では無いです。極論すれば決定問題において問題を一切見ずにランダムに答えても正答確率 1/2のモンテカルロ法になります。このモンテカルロ法の内、誤答する確率が1/2未満の定数に収まるのがBPP、1/2まで許容するのがPPで、この分野ではほぼ P=BPP、P≠PP（暗に BPP ⊂ NPも）と信じられていますが、確証はいまだに見つかっていなかったはずです。さらにNP ⊂ PPなので、そもそも「NPの難しさとは何か」という考察は、この方面では結構興味深いことになっています。

記事の修正に関しては特に異論は無いです（むしろ僕の拙文を書き直してくれるなら大歓迎）。 --U-ichi 2011年2月21日 (月) 11:28 (UTC)

NISTの出典には多項式時間に関する記述はなかったので定義を書き換えました。 Motwani & Raghavan (1995) はMathematical Subject Classificationで68Q(Theory of computing)に分類される本でRPなどのクラスの定義もその後で与えているので、出典としてはより適切かと思います。彼らは最大時間計算量に関する制約の有無をefficient Monte Carlo algorithmとMonte Carlo algorithmという語で区別しています。 --ARAKI Satoru（会話） 2016年5月23日 (月) 10:41 (UTC)