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

L (計算複雑性理論)

索引 L (計算複雑性理論)

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

16 関係: 対数対数領域還元一階述語論理チューリングマシンポインタ (プログラミング)グラフ理論神託機械非決定性チューリングマシン計算複雑性理論関数問題NL (計算複雑性理論)P (計算複雑性理論)SL (計算複雑性理論)推移閉包決定問題2004年

対数

対数(たいすう、logarithm)とは、ある数 を数 の冪乗 として表した場合の冪指数 である。この は「底を とする の対数(x to base; base logarithm of )」と呼ばれ、通常は と書き表される。また、対数 に対する は(しんすう、antilogarithm)と呼ばれる。数 に対応する対数を与える関数を考えることができ、そのような関数を対数関数と呼ぶ。対数関数は通常 と表される。 通常の対数 は真数, 底 を実数として定義されるが、実数の対数からの類推により、複素数や行列などの様々な数に対してその対数が定義されている。 実数の対数 は、底 が でない正数であり、真数 が正数である場合この条件は真数条件と呼ばれる。 について定義される。 これらの条件を満たす対数は、ある と の組に対してただ一つに定まる。 実数の対数関数 はb に対する指数関数 の逆関数である。この性質はしばしば対数関数の定義として用いられるが、歴史的には対数の出現の方が指数関数よりも先であるネイピア数 のヤコブ・ベルヌーイによる発見が1683年であり、指数関数の発見もその頃である。詳細は指数関数#歴史と概観や を参照。。 y 軸を漸近線に持つ。.

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

対数領域還元

対数領域還元(たいすうりょういきかんげん、Log-space reduction)は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。 対数領域還元は多項式時間還元よりも弱いと考えられ、'''P''' に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、'''NL''' に属する言語と'''L''' に属する言語(共に P に包含される)との間の対数領域還元は L.

新しい!!: L (計算複雑性理論)と対数領域還元 · 続きを見る »

一階述語論理

一階述語論理(いっかいじゅつごろんり、first-order predicate logic)とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理(にかいじゅつごろんり、second-order predicate logic)と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理(こうかいじゅつごろんり、higher-order predicate logic)という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.

新しい!!: L (計算複雑性理論)と一階述語論理 · 続きを見る »

チューリングマシン

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

新しい!!: L (計算複雑性理論)とチューリングマシン · 続きを見る »

ポインタ (プログラミング)

ポインタ (pointer) とは、あるオブジェクトがなんらかの論理的位置情報でアクセスできるとき、それを参照する(指し示す)ものである。有名な例としては Pascal のポインタが挙げられる。 なお、C++では、さらに独立した「参照」という機能がある。.

新しい!!: L (計算複雑性理論)とポインタ (プログラミング) · 続きを見る »

グラフ理論

ラフ理論(グラフりろん、graph theory)は、ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.

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

神託機械

託機械(しんたくきかい、oracle machine)または預言機械(よげんきかい)は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託(oracle)と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。.

新しい!!: L (計算複雑性理論)と神託機械 · 続きを見る »

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

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

新しい!!: L (計算複雑性理論)と非決定性チューリングマシン · 続きを見る »

計算複雑性理論

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

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

関数問題

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

新しい!!: L (計算複雑性理論)と関数問題 · 続きを見る »

NL (計算複雑性理論)

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

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

P (計算複雑性理論)

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

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

SL (計算複雑性理論)

計算複雑性理論におけるSLとは、USTCON問題に対数領域還元可能な問題の複雑性クラスである(Symmetric Logspace の略)。USTCON問題とは、無向グラフの2点間に経路があるかどうかを判定する問題であり、言い換えれば2つの頂点が同じ連結部分に属しているかどうかを判定する問題である。多対一還元かチューリング還元かは問われない。SLは本来は「対称性チューリング機械」を使って定義されるが、非常に複雑な定式化であるため、 実際にはUSTCON問題への還元性の方がよく使われる。 USTCON は STCON(有向到達可能性)問題の特殊ケースである。STCONは有向グラフでの2つの頂点間の経路の有無を判定する問題であり、'''NL'''-完全である。USTCON は SL-完全なので、USTCONの解法の進歩は SL にも影響がある。 2004年10月、Omer Reigngold は SL.

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

推移閉包

推移閉包(すいいへいほう、transitive closure)は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係 R を意味する。 たとえば X を人間(生死は問わない)の集合とし、「x は y の親である」という関係 xRy を考えると、その推移閉包は「x は y の先祖である」という関係 xRy である。あるいは X を空港の集合とし、「x から y への直通便が存在する」という関係 xRy を考えると、その推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係 xRy である。.

新しい!!: L (計算複雑性理論)と推移閉包 · 続きを見る »

決定問題

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

新しい!!: L (計算複雑性理論)と決定問題 · 続きを見る »

2004年

この項目では、国際的な視点に基づいた2004年について記載する。.

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

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