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

E (計算複雑性理論)と多項式時間変換

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

E (計算複雑性理論)と多項式時間変換の違い

E (計算複雑性理論) vs. 多項式時間変換

計算複雑性理論において、複雑性クラス E とは、決定性チューリング機械で 2O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2O(n)) に等しい。 E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。. 多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。.

E (計算複雑性理論)と多項式時間変換間の類似点

E (計算複雑性理論)と多項式時間変換は（ユニオンペディアに）共通で3ものを持っています: チューリングマシン、EXPTIME、計算複雑性理論。

チューリングマシン

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

E (計算複雑性理論)とチューリングマシン · チューリングマシンと多項式時間変換 · 続きを見る »

EXPTIME

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

E (計算複雑性理論)とEXPTIME · EXPTIMEと多項式時間変換 · 続きを見る »

計算複雑性理論

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

E (計算複雑性理論)と計算複雑性理論 · 多項式時間変換と計算複雑性理論 · 続きを見る »

上記のリストは以下の質問に答えます

E (計算複雑性理論)と多項式時間変換の間の比較

多項式時間変換が17を有しているE (計算複雑性理論)は、8の関係を有しています。 彼らは一般的な3で持っているように、ジャカード指数は12.00%です = 3 / (8 + 17)。

参考文献

この記事では、E (計算複雑性理論)と多項式時間変換との関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください:

ヘイ！私たちは今、Facebook上です！ »