ブラウザよりも高速アクセス！
19 関係: 多項式時間、乱択アルゴリズム、チューリングマシン、モンテカルロ法、ランダム、ラスベガス法、アルゴリズム、BQP、確率的チューリング機械、複雑性クラス、計算複雑性理論、量子コンピュータ、NP、P (計算複雑性理論)、PH (計算複雑性理論)、PP (計算複雑性理論)、RP (計算複雑性理論)、決定問題、指数関数。
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: BPP (計算複雑性理論)と多項式時間 · 続きを見る »
乱択アルゴリズム
乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.
新しい！!: BPP (計算複雑性理論)と乱択アルゴリズム · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: BPP (計算複雑性理論)とチューリングマシン · 続きを見る »
モンテカルロ法
モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。.
新しい！!: 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 (計算複雑性理論)とラスベガス法 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: BPP (計算複雑性理論)とアルゴリズム · 続きを見る »
BQP
計算複雑性理論において、BQPとは、量子コンピュータによって誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Quantum Polynomial time の頭文字をとったものである。ある問題がBQPに属すなら、高い確率で正答を返し、多項式時間で実行可能な、量子コンピュータのためのアルゴリズムが存在する。そのアルゴリズムは解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 '''BPP'''と同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化してもBQPは変化しない。.
新しい！!: BPP (計算複雑性理論)とBQP · 続きを見る »
確率的チューリング機械
率的チューリング機械（かくりつてきチューリングきかい、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 (計算複雑性理論)と計算複雑性理論 · 続きを見る »
量子コンピュータ
量子コンピュータ （りょうしコンピュータ、英語：quantum computer） は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ（以下「古典コンピュータ」）の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下）で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.
新しい！!: BPP (計算複雑性理論)と量子コンピュータ · 続きを見る »
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。.
新しい！!: BPP (計算複雑性理論)とNP · 続きを見る »
P (計算複雑性理論)
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。.
新しい！!: BPP (計算複雑性理論)とP (計算複雑性理論) · 続きを見る »
PH (計算複雑性理論)
計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP（'''PP'''をオラクルとして持つ神託機械で多項式時間で解ける問題のクラス）、P#P（戸田の定理による）、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P.
新しい！!: BPP (計算複雑性理論)とPH (計算複雑性理論) · 続きを見る »
PP (計算複雑性理論)
計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。.
新しい！!: BPP (計算複雑性理論)とPP (計算複雑性理論) · 続きを見る »
RP (計算複雑性理論)
計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。.
新しい！!: BPP (計算複雑性理論)とRP (計算複雑性理論) · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: BPP (計算複雑性理論)と決定問題 · 続きを見る »
指数関数
実解析における指数関数（しすうかんすう、exponential function）は、冪における指数 を変数として、その定義域を主に実数の全体へ拡張して定義される初等超越関数の一種である。対数関数の逆関数であるため、逆対数 と呼ばれることもある。自然科学において、指数関数は量の増加度に関する数学的な記述を与えるものとして用いられる（や指数関数的減衰の項を参照）。 一般に、 かつ なる定数 に関して、（主に実数の上を亙る）変数 を へ送る関数は、「a を'''底'''とする指数函数」と呼ばれる。「指数関数」との名称は、与えられた底に関して冪指数を変数とする関数であることを示唆するものであり、冪指数を固定して底を独立変数とする冪関数とは対照的である。 しばしば、より狭義の関数を意図して単に「指数関数」と呼ぶこともある。そのような標準的な (the) 指数関数（あるいはより明示的に「自然指数関数」）はネイピア数 を底とする関数 である。これを のようにも書く。この関数は、導関数が自分自身に一致するなど、他の指数関数と比べて著しい性質を持つ。底 を他の底 に取り換えるには自然対数 を用いて、等式 を適用すればよいから、以下本項では主に自然指数関数について記述し、多くの場合「指数関数」は自然指数関数の意味で用いる。.
新しい！!: BPP (計算複雑性理論)と指数関数 · 続きを見る »
