BPP (計算複雑性理論)とモンテカルロ法

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

BPP (計算複雑性理論)とモンテカルロ法の違い

BPP (計算複雑性理論) vs. モンテカルロ法

計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。. モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。.

乱択アルゴリズム

乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.

BPP (計算複雑性理論)と乱択アルゴリズム · モンテカルロ法と乱択アルゴリズム · 続きを見る »

ランダム

ランダム（random）とは、事象の発生に法則性（規則性）がなく、な状態である。ランダムネス（randomness）、無作為性（むさくいせい）ともいう。 事象・記号などのランダムな列には秩序がなく、理解可能なパターンや組み合わせに従わない。個々のランダムな事象は定義上予測不可能であるが、多くの場合、何度も試行した場合の結果の頻度は予測可能である。例えば、2つのサイコロを投げるとき、1回ごとの出目は予測できないが、合計が7になる頻度は4になる頻度の2倍になる。この見方では、ランダム性とは結果の不確実性の尺度であり、確率・情報エントロピーの概念に適用される。 数学、確率、統計の分野では、ランダム性の正式な定義が使用される。統計では、事象空間の起こり得る結果に数値を割り当てたものを確率変数(random variable)という。この関連付けは、事象の確率の識別および計算を容易にする。確率変数の列を(random sequence)という。ランダム過程（不規則過程、確率過程）は、結果が決定論的パターンに従わず、確率分布によって記述される進化に従う確率変数の列である。これらの構造と他の構造は、確率論や様々なランダム性の応用に非常に有用である。 ランダム性は、よく定義された統計的特性を示すために統計で最も頻繁に使用される。ランダムな入力（や擬似乱数発生器など）に依存するモンテカルロ法は、計算科学などの科学において重要な技術である。これに対し、では乱数列ではなく一様分布列を使用している。 無作為抽出(random selection)は、ある項目を選択する確率が母集団内におけるその項目の割合と一致している集団から項目を選択する方法である。例えば、赤い石10個と青い石90個を入れた袋に入れた場合、この袋から何らかのランダム選択メカニズムによって石を1個選択した時にそれが赤い石である確率は1/10である。しかし、ランダム選択メカニズムによって実際に10個の石を選択したときに、それが赤1個・青9個であるとは限らない。母集団が識別可能な項目で構成されている状況では、ランダム選択メカニズムは、選択される項目に等しい確率を必要とする。つまり、選択プロセスが、母集団の各メンバー（例えば、研究対象）が選択される確率が同じである場合、選択プロセスはランダムであると言うことができる。.

BPP (計算複雑性理論)とランダム · モンテカルロ法とランダム · 続きを見る »

ラスベガス法

ラスベガス法（Las Vegas algorithm）は、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は(efficient)であるという。ラスベガス法の単純な例にランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。.

BPP (計算複雑性理論)とラスベガス法 · モンテカルロ法とラスベガス法 · 続きを見る »

確率的チューリング機械

率的チューリング機械（かくりつてきチューリングきかい、Probabilistic Turing machine）は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。 各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット（一般に '1' と '0'）についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。 結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。 従って、確率的チューリング機械での文字列の受理/不受理は、通常とは異なった形で定義される。この定義の違いによって、様々な多項式時間の確率的な複雑性クラスが生じる。例えば、'''RP'''、Co-RP、'''BPP'''、ZPP などである。制約を多項式時間ではなく対数領域とした場合は、LP、Co-RL、BPL、ZPL がある。また、両方を制約を課した場合は、RLP、Co-RPL、BPLP、ZPLP がある。 確率的計算は対話型証明系の多くのクラスの定義においても重要である。この場合、検査機構（verifier）は全能の証明機構（prover）にだまされないためにランダム性を必要とする。例えば、IPクラスは PSPACE に等しいが、検査機構でのランダム性を排除すると NP と等しくなってしまう。PSPACE と NP の関係は正確には未だ確定していないが、おそらく NP の方が小さいと考えられている。 計算複雑性理論の課題の1つとして、「ランダム性は計算能力を向上させるか?」という問題がある。つまり、確率的チューリング機械で多項式時間で解ける問題があるとき、それが決定性チューリング機械では多項式時間で解けないと言えるだろうか? それとも、決定性チューリング機械で確率的チューリング機械をシミュレートして、高々多項式程度の低速化で問題を解けるだろうか? 現在、多くの研究者は後者（P.

BPP (計算複雑性理論)と確率的チューリング機械 · モンテカルロ法と確率的チューリング機械 · 続きを見る »

複雑性クラス

複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.

BPP (計算複雑性理論)と複雑性クラス · モンテカルロ法と複雑性クラス · 続きを見る »

計算複雑性理論

計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.

BPP (計算複雑性理論)と計算複雑性理論 · モンテカルロ法と計算複雑性理論 · 続きを見る »

NP

NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。.

BPP (計算複雑性理論)とNP · NPとモンテカルロ法 · 続きを見る »

P (計算複雑性理論)

計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。.

BPP (計算複雑性理論)とP (計算複雑性理論) · P (計算複雑性理論)とモンテカルロ法 · 続きを見る »

PP (計算複雑性理論)

計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。.

BPP (計算複雑性理論)とPP (計算複雑性理論) · PP (計算複雑性理論)とモンテカルロ法 · 続きを見る »

RP (計算複雑性理論)

計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。.

BPP (計算複雑性理論)とRP (計算複雑性理論) · RP (計算複雑性理論)とモンテカルロ法 · 続きを見る »