計算理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/31 03:06 UTC 版)
計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り返し、実行時間を犠牲にすれば誤答する確率をいくらでも小さくすることができる。またモンテカルロ法の中でも任意の入力に対して最大時間計算量の上界が入力サイズの多項式で与えられるものを効率的モンテカルロ法という。 なお、これとは対照的に理論上必ずしも終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。 計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。これらのクラスと P や NP との関連性を解明していくことによって、モンテカルロ法のようにランダム性を含むアルゴリズムによって解ける問題の範囲が拡大しているのか（P ≠ BPP なのか）、それとも単に決定的アルゴリズムで解ける問題の多項式時間の次数を減らしているだけなのか（P=BPP なのか）は計算複雑性理論における主要課題の1つである。現在、NP ⊂ PP 、RP ⊆ NPであることは解っているが BPP と NPとの関係は解っていない。
※この「計算理論」の解説は、「モンテカルロ法」の解説の一部です。
「計算理論」を含む「モンテカルロ法」の記事については、「モンテカルロ法」の概要を参照ください。
Weblioに収録されているすべての辞書から計算理論を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算理論
を検索
- 計算理論のページへのリンク
