ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
無料
ブラウザよりも高速アクセス!
 

複雑性クラス

索引 複雑性クラス

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

61 関係: 原始再帰関数多項式階層多項式時間対話型証明系帰納的可算言語帰納言語乱択アルゴリズム交替性チューリング機械チューリングマシンランダウの記号ブラムの公理BPP (計算複雑性理論)BQPCo-NP算術的階層DSPACEDTIMEE (計算複雑性理論)ELEMENTARYESPACEEXPSPACEEXPTIME非決定性チューリングマシン複雑性計算可能性理論計算モデル計算複雑性理論記述計算量部分集合関数問題還元 (計算複雑性理論)量子コンピュータL (計算複雑性理論)LOGCFLNC (計算複雑性理論)NEXPTIMENL (計算複雑性理論)NPNP完全問題NP困難NSPACENTIMEP (計算複雑性理論)P≠NP予想PH (計算複雑性理論)PP (計算複雑性理論)PR (計算複雑性理論)PSPACER (計算複雑性理論)RE (計算複雑性理論)...RP (計算複雑性理論)Sharp-PUP (計算複雑性理論)ZPP抽象機械正規文法決定問題文脈依存文法文脈自由言語文脈自由文法数理論理学 インデックスを展開 (11 もっと) »

原始再帰関数

原始再帰関数(げんしさいきかんすう、)とは、原始再帰と合成で定義される関数であり、再帰関数(計算可能関数)の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている(限界の節を参照)。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスはwhileプログラムでwhileループを使用せずに計算できる(すなわちloopプログラムで計算可能な)関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。.

新しい!!: 複雑性クラスと原始再帰関数 · 続きを見る »

多項式階層

多項式階層(たこうしきかいそう、Polynomial hierarchy)は、計算量理論における計算量の階層であり、神託機械を使って '''P'''、NP、co-'''NP''' を一般化させて定義されるものである。.

新しい!!: 複雑性クラスと多項式階層 · 続きを見る »

多項式時間

多項式時間(たこうしきじかん)とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.

新しい!!: 複雑性クラスと多項式時間 · 続きを見る »

対話型証明系

対話型証明系(たいわがたしょうめいけい、Interactive proof system)は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。.

新しい!!: 複雑性クラスと対話型証明系 · 続きを見る »

帰納的可算言語

帰納的可算言語(きのうてきかさんげんご、Recursively enumerable language)は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語(Partially Decidable Language)、チューリング受理性言語(Turing-recognizable Language)とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。.

新しい!!: 複雑性クラスと帰納的可算言語 · 続きを見る »

帰納言語

帰納言語(きのうげんご、Recursive language)は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない(Chomsky 1959)。.

新しい!!: 複雑性クラスと帰納言語 · 続きを見る »

乱択アルゴリズム

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

新しい!!: 複雑性クラスと乱択アルゴリズム · 続きを見る »

交替性チューリング機械

交替性チューリング機械(こうたいせいチューリングきかい、Alternating Turing Machine, ATM)は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-'''NP''' の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。.

新しい!!: 複雑性クラスと交替性チューリング機械 · 続きを見る »

チューリングマシン

チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.

新しい!!: 複雑性クラスとチューリングマシン · 続きを見る »

ランダウの記号

ランダウの記号(ランダウのきごう、Landau symbol)は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (オーもしくはオミクロン Ο。数字の0ではない)を用いることから(ランダウの)O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー(Order)から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.

新しい!!: 複雑性クラスとランダウの記号 · 続きを見る »

ブラムの公理

計算複雑性理論におけるブラムの公理(ブラムのこうり、Blum axioms)またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。 重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。.

新しい!!: 複雑性クラスとブラムの公理 · 続きを見る »

BPP (計算複雑性理論)

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

新しい!!: 複雑性クラスとBPP (計算複雑性理論) · 続きを見る »

BQP

計算複雑性理論において、BQPとは、量子コンピュータによって誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Quantum Polynomial time の頭文字をとったものである。ある問題がBQPに属すなら、高い確率で正答を返し、多項式時間で実行可能な、量子コンピュータのためのアルゴリズムが存在する。そのアルゴリズムは解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 '''BPP'''と同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化してもBQPは変化しない。.

新しい!!: 複雑性クラスとBQP · 続きを見る »

Co-NP

co-NPとは計算量理論における問題クラスの一つである。.

新しい!!: 複雑性クラスとCo-NP · 続きを見る »

算術的階層

算術的階層(さんじゅつてきかいそう、Arithmetical hierarchy)は、数理論理学において、集合を定義する式の複雑さに基づいて、その集合を分類した階層である。クリーネ階層(Kleene hierarchy)とも。このような分類が可能な集合は算術的である。 算術的階層は、再帰理論やペアノ算術のような形式理論の研究で重要である。 算術的階層での式や集合の分類の拡張として、超算術的階層や解析的階層がある。.

新しい!!: 複雑性クラスと算術的階層 · 続きを見る »

DSPACE

DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース(プログラムの実行に必要な物理的メモリ量)と直接対応することから、最もよく研究されている複雑性の尺度の1つである。.

新しい!!: 複雑性クラスとDSPACE · 続きを見る »

DTIME

DTIME(またはTIME)は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量(ステップ数)を表す。実際のリソース(プログラムの実行にかかる時間)と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 n の問題を解くのに O(f(n)) の計算時間がかかる場合、その複雑性クラスは \text(f(n))(または \text(f(n)))となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。.

新しい!!: 複雑性クラスとDTIME · 続きを見る »

E (計算複雑性理論)

計算複雑性理論において、複雑性クラス E とは、決定性チューリング機械で 2O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2O(n)) に等しい。 E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。.

新しい!!: 複雑性クラスとE (計算複雑性理論) · 続きを見る »

ELEMENTARY

計算複雑性理論において ELEMENTARY とはの和集合で表される複雑性クラスである。 クラス ELEMENTARY に属す関数は初等帰納的(しょとうきのうてき、elementary recursive)あるいは単に初等的と呼ばれる。この名称はによる造語である。 帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。 ELEMENTARY は指数関数の定数回の入れ子(例えば 2^)を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの(例えばテトレーション)を含む。.

新しい!!: 複雑性クラスとELEMENTARY · 続きを見る »

ESPACE

計算複雑性理論において、複雑性クラス ESPACE とは、決定性チューリング機械で 2O(n) の領域で解ける決定問題の集合である。 EXPSPACE も参照されたい。.

新しい!!: 複雑性クラスとESPACE · 続きを見る »

EXPSPACE

計算複雑性理論において、複雑性クラス EXPSPACE とは、決定性チューリング機械で O(2p(n)) の領域を使って解ける全決定問題の集合である。ここで、p(n) は n の多項式関数である。p(n) を一次関数に限定する場合もあるが、通常そのようなクラスは ESPACE と呼ばれる。 DSPACEの記法では以下のように表される。 EXPSPACE完全な決定問題とは、EXPSPACE に属し、かつ全ての EXPSPACE に属する問題を多項式時間多対一還元によってその問題に帰着させることができる場合を指す。換言すれば、多項式時間アルゴリズムによって、ある問題から別の問題へ解を変えずに変換可能である。EXPSPACE完全問題は、EXPSPACEの中でも最も難しい問題とされる。 EXPSPACE は PSPACE、NP、P を真に包含する。また、EXPTIME をも真に包含すると考えられている。 EXPSPACE完全な問題の例として、2つの正規表現が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子(和集合、連結、クリーネ閉包(ゼロ個以上のコピー)、平方(2つのコピー))に制限される。 クリーネ閉包を除くと、この問題は NEXPTIME完全となる。これは EXPTIME完全に似ているが、決定性ではなく非決定性チューリング機械で定義される。 また1980年、L.

新しい!!: 複雑性クラスとEXPSPACE · 続きを見る »

EXPTIME

EXPTIME(EXPとも)は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。 DTIMEでは次のように表される。 以下の関係が知られている。 また、時間階層定理と領域階層定理により、次のようになる。 従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P.

新しい!!: 複雑性クラスとEXPTIME · 続きを見る »

非決定性チューリングマシン

非決定性チューリング機械(ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM)は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。.

新しい!!: 複雑性クラスと非決定性チューリングマシン · 続きを見る »

複雑性

複雑性(ふくざつせい、complexity)という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.

新しい!!: 複雑性クラスと複雑性 · 続きを見る »

計算可能性理論

計算可能性理論(けいさんかのうせいりろん、computability theory)では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.

新しい!!: 複雑性クラスと計算可能性理論 · 続きを見る »

計算モデル

計算モデル(model of computation)とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械(abstract machine)と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ(要するにいわゆるノイマン型)を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない(実装する予定のない)マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.

新しい!!: 複雑性クラスと計算モデル · 続きを見る »

計算複雑性理論

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

新しい!!: 複雑性クラスと計算複雑性理論 · 続きを見る »

記述計算量

記述計算量(きじゅつけいさんりょう、Descriptive complexity)は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、'''PH'''は二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。.

新しい!!: 複雑性クラスと記述計算量 · 続きを見る »

部分集合

集合 A が集合 B の部分集合(ぶぶんしゅうごう、subset; 下位集合)であるとは、A が B の一部(あるいは全部)の要素だけからなることである。A が B の一部分であるという意味で部分集合という。二つの集合の一方が他方の部分集合であるとき、この二つの集合の間に包含関係があるという。.

新しい!!: 複雑性クラスと部分集合 · 続きを見る »

関数問題

関数問題(かんすうもんだい、function problem)とは、計算量理論において、各入力に対してある出力を返す形式の問題をいう。評価問題とも呼ばれる。文字列上の写像\Sigma ^* \to \Sigma ^*で表される。主に判定問題(関数問題のうち出力が\であるようなもの)と対比して用いられることが多い。.

新しい!!: 複雑性クラスと関数問題 · 続きを見る »

還元 (計算複雑性理論)

還元(かんげん、Reduction)とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。 直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。.

新しい!!: 複雑性クラスと還元 (計算複雑性理論) · 続きを見る »

量子コンピュータ

量子コンピュータ (りょうしコンピュータ、英語:quantum computer) は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ(以下「古典コンピュータ」)の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下)で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.

新しい!!: 複雑性クラスと量子コンピュータ · 続きを見る »

L (計算複雑性理論)

計算量理論において、Lとは、決定性チューリングマシンで対数規模の領域(メモリ)を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。 Lと関連する計算量に'''NL'''がある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、\mathrm \subseteq \mathrm が成り立つ。 また、O(log n) の領域を使用する決定機械は時間 2O(log n).

新しい!!: 複雑性クラスとL (計算複雑性理論) · 続きを見る »

LOGCFL

計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。 '''NL'''と'''AC'''1の間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。.

新しい!!: 複雑性クラスとLOGCFL · 続きを見る »

NC (計算複雑性理論)

計算複雑性理論において、NC(Nick's Class)とは多項式個数のプロセッサで構成される並列計算機で,問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(nk)個の並列プロセッサを使って O((log n)c) の時間で解ける(c と k は定数)。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。 クラス P と同様、NC に属する問題は並列計算機で効率的に解くことができると見なされている。並列計算機は通常の計算機でシミュレート可能であるため、NC は P に含まれる。NC.

新しい!!: 複雑性クラスとNC (計算複雑性理論) · 続きを見る »

NEXPTIME

計算複雑性理論において、複雑性クラス NEXPTIME(NEXP)とは、非決定性チューリング機械で O(2p(n)) の時間(p(n) は任意の多項式)と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit(簡潔回路)がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合は'''NP'''完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、'''P'''.

新しい!!: 複雑性クラスとNEXPTIME · 続きを見る »

NL (計算複雑性理論)

NL(えぬえる、Nondeterministic Logarithmic-space)は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL.

新しい!!: 複雑性クラスとNL (計算複雑性理論) · 続きを見る »

NP

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

新しい!!: 複雑性クラスとNP · 続きを見る »

NP完全問題

NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック(Stephen Cook (1971).

新しい!!: 複雑性クラスとNP完全問題 · 続きを見る »

NP困難

NP完全、'''NP困難'''の相関を表すベン図 NP困難(エヌピーこんなん、NP-hard)とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える(以下は定義ではなく主張)。.

新しい!!: 複雑性クラスとNP困難 · 続きを見る »

NSPACE

計算複雑性理論において、複雑性クラス NSPACE(f(n)) とは、非決定性チューリング機械で領域 O(f(n)) と無制限の時間で解ける決定問題の集合である。DSPACEの非決定性バージョンである。 複雑性クラス NPSPACE は NSPACE を使って以下のように定義できる。.

新しい!!: 複雑性クラスとNSPACE · 続きを見る »

NTIME

NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間(領域)を使って解くことが出来る決定問題の集合である。 よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。 同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性時間階層定理によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。 Category:計算複雑性理論 Category:数学に関する記事.

新しい!!: 複雑性クラスとNTIME · 続きを見る »

P (計算複雑性理論)

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

新しい!!: 複雑性クラスとP (計算複雑性理論) · 続きを見る »

P≠NP予想

P≠NP予想(P≠NPよそう、)は、計算複雑性理論(計算量理論)におけるクラスPとクラスNPが等しくないという予想である。P対NP問題(PたいNPもんだい、)と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。.

新しい!!: 複雑性クラスとP≠NP予想 · 続きを見る »

PH (計算複雑性理論)

計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP('''PP'''をオラクルとして持つ神託機械で多項式時間で解ける問題のクラス)、P#P(戸田の定理による)、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P.

新しい!!: 複雑性クラスとPH (計算複雑性理論) · 続きを見る »

PP (計算複雑性理論)

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

新しい!!: 複雑性クラスとPP (計算複雑性理論) · 続きを見る »

PR (計算複雑性理論)

計算複雑性理論において、複雑性クラス PR とは、全ての原始再帰関数の集合、あるいは原始再帰関数で決定される全ての形式言語の集合である。これには、加算、乗算、冪乗、tetration などが含まれる。 原始再帰的でない関数の例としてアッカーマン関数があり、それにより PR が厳密に R に含まれることがわかる。 PR に属する関数は明示的に枚挙可能だが、R の場合は不可能である(チューリングマシンの停止問題が決定不能であるため)。すなわち、PR は構文的クラスであり、R は意味論的クラスである。 一方、任意の帰納的可算集合(REも参照)を原始再帰関数を次のように使って枚挙可能である。入力 (M, k) を与えたとき(M はチューリングマシン、k は整数)、M が k ステップ以内に停止するなら M を出力するものとする。そうでない場合は何も出力しない。すると (M, k) の考えられる全ての組合せの入力について、それらの出力の和集合は、停止する M の集合に他ならない。.

新しい!!: 複雑性クラスとPR (計算複雑性理論) · 続きを見る »

PSPACE

PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。.

新しい!!: 複雑性クラスとPSPACE · 続きを見る »

R (計算複雑性理論)

計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる(チャーチ=チューリングのテーゼ)。 任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは RE を使って RE \cap coRE と定義できる。.

新しい!!: 複雑性クラスとR (計算複雑性理論) · 続きを見る »

RE (計算複雑性理論)

計算複雑性理論において、複雑性クラス RE(recursively enumerable)とは、チューリングマシン(Turing machine)で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。 RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'(枚挙可能)と呼ばれる。 解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。 RE の各要素は帰納的可算集合(recursively enumerable set)である。.

新しい!!: 複雑性クラスとRE (計算複雑性理論) · 続きを見る »

RP (計算複雑性理論)

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

新しい!!: 複雑性クラスとRP (計算複雑性理論) · 続きを見る »

Sharp-P

計算複雑性理論において、複雑性クラス ♯P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。 NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。.

新しい!!: 複雑性クラスとSharp-P · 続きを見る »

UP (計算複雑性理論)

計算複雑性理論において、複雑性クラス UP ("Unambiguous Non-deterministic Polynomial-time") とは、入力に対して高々1つの受容経路を持つ非決定性チューリング機械で多項式時間で解ける決定問題の集合である。UP は Pを包含し、NP に包含される。その際、P ≠ UP または UP ≠ NP(あるいは両方)と考えられている(P≠NP予想)。多くの学者は P とも NP とも等しくないと予想している。 別の定式化として、解の検証が決定性チューリング機械で多項式時間で行える場合にのみ、ある言語が NP に含まれると言える。同様に、ある言語が UP に含まれるとは、解を多項式時間で検証でき、かつその検証機械がそれぞれの具体的問題について高々1つの解のみ受容することである。形式的に表せば、言語 L が UP に属するのは、2入力の多項式時間アルゴリズム A と定数 c があって、次が成り立つ場合である(アルゴリズム A は L を多項式時間で検証する)。 Category:計算複雑性理論 Category:数学に関する記事.

新しい!!: 複雑性クラスとUP (計算複雑性理論) · 続きを見る »

ZPP

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

新しい!!: 複雑性クラスとZPP · 続きを見る »

抽象機械

抽象機械(抽象コンピュータとも呼ばれる)は、オートマトンで利用される、コンピュータハードウェアやソフトウェアシステムの理論上モデルである。 計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間パラダイムを仮定している。.

新しい!!: 複雑性クラスと抽象機械 · 続きを見る »

正規文法

正規文法(せいきぶんぽう、Regular Grammar)は、形式文法における右正規文法と左正規文法の総称。 右正規文法(みぎせいきぶんぽう、Right Regular Grammar)は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。.

新しい!!: 複雑性クラスと正規文法 · 続きを見る »

決定問題

決定問題(けっていもんだい、decision problem)とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか(充足可能性問題)、与えられた自然数が素数か否か(素数判定問題)、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題(function problem)と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.

新しい!!: 複雑性クラスと決定問題 · 続きを見る »

文脈依存文法

文脈依存文法(ぶんみゃくいぞんぶんぽう、Context-sensitive Grammar)は、形式文法 G.

新しい!!: 複雑性クラスと文脈依存文法 · 続きを見る »

文脈自由言語

文脈自由言語(ぶんみゃくじゆうげんご)とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。.

新しい!!: 複雑性クラスと文脈自由言語 · 続きを見る »

文脈自由文法

文脈自由文法(ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG)は、形式言語の理論(特に、生成文法)において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の(0個を含む)任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている(「文脈無用」という訳の提案もある)。文脈自由文法によって生成される形式言語を文脈自由言語という。.

新しい!!: 複雑性クラスと文脈自由文法 · 続きを見る »

数理論理学

数理論理学(mathematische Logik、mathematical logic)は、論理学(形式論理学)の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学(とくに)における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか(逆数学のように)ということに焦点を当てている。.

新しい!!: 複雑性クラスと数理論理学 · 続きを見る »

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »