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

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

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

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

計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。. モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。.

乱択アルゴリズム

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

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

BPP (計算複雑性理論)

計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。.

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

計算複雑性理論

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

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

NP

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

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

RP (計算複雑性理論)

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

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