ブラウザよりも高速アクセス！
23 関係: 多項式時間、多項式時間変換、交替性チューリング機械、チューリングマシン、チェッカー、チェス、ランダウの記号、アルゴリズム、グラフ理論、囲碁、DTIME、隣接行列、EXPSPACE、非決定性チューリングマシン、計算可能性理論、計算複雑性理論、集合、NEXPTIME、NP、P (計算複雑性理論)、PSPACE、決定問題、指数関数時間。
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: EXPTIMEと多項式時間 · 続きを見る »
多項式時間変換
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。.
新しい！!: EXPTIMEと多項式時間変換 · 続きを見る »
交替性チューリング機械
交替性チューリング機械（こうたいせいチューリングきかい、Alternating Turing Machine, ATM）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-'''NP''' の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。.
新しい！!: EXPTIMEと交替性チューリング機械 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: EXPTIMEとチューリングマシン · 続きを見る »
チェッカー
ボードゲームのチェッカー（）は、相手の駒を取り合うゲーム。色違いの丸い駒を使用する。縦横8マスのチェスボードを用いるものと、9マス、10マスの独自のボードを用いるものがある。ドラフツ（draughts）、西洋碁とも呼ばれる。.
新しい！!: EXPTIMEとチェッカー · 続きを見る »
チェス
チェスの駒 チェス（chess、شطرنج šaṭranj シャトランジ）は、2人で行うボードゲーム、マインドスポーツの一種である。先手・後手それぞれ6種類16個の駒を使って、敵のキングを追いつめるゲームである。その文化的背景などから、チェスプレイヤーの間では、チェスはゲームであると同時に「スポーツ」でも「芸術」でも「科学」でもあるとされ、ゲームに勝つためにはこれらのセンスを総合する能力が必要であると言われている。.
新しい！!: EXPTIMEとチェス · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: EXPTIMEとランダウの記号 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: EXPTIMEとアルゴリズム · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: EXPTIMEとグラフ理論 · 続きを見る »
囲碁
囲碁（いご）とは、2人で行うボードゲームの一種。交互に盤上に石を置いていき、自分の石で囲んだ領域の広さを争う。単に碁（ご）とも呼ばれる。.
新しい！!: EXPTIMEと囲碁 · 続きを見る »
DTIME
DTIME（またはTIME）は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量（ステップ数）を表す。実際のリソース（プログラムの実行にかかる時間）と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 n の問題を解くのに O(f(n)) の計算時間がかかる場合、その複雑性クラスは \text(f(n))（または \text(f(n))）となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。.
新しい！!: EXPTIMEとDTIME · 続きを見る »
隣接行列
隣接行列（りんせつぎょうれつ、adjacency matrix）とは、における基本的な概念で、グラフの頂点と頂点の隣接関係を表わす正方行列である。 頂点集合を とする有限無向グラフ に対して、その隣接行列 とは（頂点集合によって添字づけられた） 次正方行列であって、その 成分 は頂点 と頂点 を結ぶ枝の数で定義される。これによりグラフ の固有多項式やスペクトルがそれぞれ隣接行列 の固有多項式やスペクトルとして定義される。これらはグラフの不変量である（隣接行列そのものは頂点集合上の置換を除いてしか定まらない）。 有向グラフの場合、 から に向かう枝があるときのみ 成分を 1 に、そうでないとき 成分を 0 にする。また、枝に重みがついているグラフの場合は、 成分を重みとする。.
新しい！!: EXPTIMEと隣接行列 · 続きを見る »
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.
新しい！!: EXPTIMEとEXPSPACE · 続きを見る »
非決定性チューリングマシン
非決定性チューリング機械（ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。.
新しい！!: EXPTIMEと非決定性チューリングマシン · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: EXPTIMEと計算可能性理論 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: EXPTIMEと計算複雑性理論 · 続きを見る »
集合
数学における集合 (しゅうごう、set, ensemble, Menge) とは、大雑把に言えばいくつかの「もの」からなる「集まり」である。集合を構成する個々の「もの」のことを元 (げん、; 要素) という。 集合は、集合論のみならず現代数学全体における最も基本的な概念の一つであり、現代数学のほとんどが集合と写像の言葉で書かれていると言ってよい。 慣例的に、ある種の集合が系 (けい、) や族 (ぞく、) などと呼ばれることもある。実際には、これらの呼び名に本質的な違いはないが細かなニュアンスの違いを含むと考えられている。たとえば、方程式系（「相互に連立する」方程式の集合）、集合族（「一定の規則に基づく」集合の集合）、加法族（「加法的な性質を持つ」集合族）など。.
新しい！!: EXPTIMEと集合 · 続きを見る »
NEXPTIME
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合は'''NP'''完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、'''P'''.
新しい！!: EXPTIMEとNEXPTIME · 続きを見る »
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。.
新しい！!: EXPTIMEとNP · 続きを見る »
P (計算複雑性理論)
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。.
新しい！!: EXPTIMEとP (計算複雑性理論) · 続きを見る »
PSPACE
PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。.
新しい！!: EXPTIMEとPSPACE · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: EXPTIMEと決定問題 · 続きを見る »
指数関数時間
指数関数時間（しすうかんすうじかん）あるいは指数時間（しすうじかん）とは、計算理論において指数関数を用いてあらわされる計算時間。計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。 一般に指数関数時間やその以上のアルゴリズムは時間がかかりすぎるので実用には適さない。そのようなアルゴリズムは特殊な場合にしか使われない。.
新しい！!: EXPTIMEと指数関数時間 · 続きを見る »
