E (計算複雑性理論)とEXPTIME間の類似点
E (計算複雑性理論)とEXPTIMEは(ユニオンペディアに)共通で6ものを持っています: 多項式時間変換、チューリングマシン、ランダウの記号、DTIME、計算複雑性理論、決定問題。
多項式時間変換
多項式時間変換(たこうしきじかんへんかん、polynomial-time reduction)は計算量理論の一概念である。多項式時間帰着(たこうしきじかんきちゃく)、多項式時間還元(たこうしきじかんかんげん)ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。.
E (計算複雑性理論)と多項式時間変換 · EXPTIMEと多項式時間変換 ·
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
E (計算複雑性理論)とチューリングマシン · EXPTIMEとチューリングマシン ·
ランダウの記号
ランダウの記号(ランダウのきごう、Landau symbol)は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O (オーもしくはオミクロン Ο。数字の0ではない)を用いることから(ランダウの)O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー(Order)から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
E (計算複雑性理論)とランダウの記号 · EXPTIMEとランダウの記号 ·
DTIME
DTIME(またはTIME)は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量(ステップ数)を表す。実際のリソース(プログラムの実行にかかる時間)と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 n の問題を解くのに O(f(n)) の計算時間がかかる場合、その複雑性クラスは \text(f(n))(または \text(f(n)))となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。.
DTIMEとE (計算複雑性理論) · DTIMEとEXPTIME ·
計算複雑性理論
計算複雑性理論(けいさんふくざつせいりろん、computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
E (計算複雑性理論)と計算複雑性理論 · EXPTIMEと計算複雑性理論 ·
決定問題
決定問題(けっていもんだい、decision problem)とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか(充足可能性問題)、与えられた自然数が素数か否か(素数判定問題)、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題(function problem)と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
上記のリストは以下の質問に答えます
- 何E (計算複雑性理論)とEXPTIMEことは共通しています
- 何がE (計算複雑性理論)とEXPTIME間の類似点があります
E (計算複雑性理論)とEXPTIMEの間の比較
EXPTIMEが23を有しているE (計算複雑性理論)は、8の関係を有しています。 彼らは一般的な6で持っているように、ジャカード指数は19.35%です = 6 / (8 + 23)。
参考文献
この記事では、E (計算複雑性理論)とEXPTIMEとの関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください: