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

NC (計算複雑性理論)

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

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

13 関係: 並列ランダムアクセス機械並列計算交替性チューリング機械スティーブン・クック複雑性クラス計算モデル計算複雑性理論論理回路L (計算複雑性理論)NL (計算複雑性理論)NP完全問題P (計算複雑性理論)決定問題

並列ランダムアクセス機械

並列ランダムアクセス機械(へいれつランダムアクセスきかい、Parallel Random Access Machine, PRAM)は、並列コンピューティングに適用可能なアルゴリズムを設計するための抽象機械である。同期や通信といった細かな部分を省き、並行性をいかに引き出すかに集中することが可能となる。フリンの分類によれば、PRAM は MIMD 型コンピュータに相当する。.

新しい!!: NC (計算複雑性理論)と並列ランダムアクセス機械 · 続きを見る »

並列計算

並列計算(へいれつけいさん、parallel computing)は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算(へいこうけいさん)があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.

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

交替性チューリング機械

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

新しい!!: NC (計算複雑性理論)と交替性チューリング機械 · 続きを見る »

スティーブン・クック

ティーブン・クック(Stephen A. Cook, 1939年12月14日 - )は、米国・カナダの計算機科学者・数学者。専門は計算理論、特に計算複雑性理論の論理学的側面やの研究に従事している。2012年現在、トロント大学計算機科学科と数学科の教授である。.

新しい!!: NC (計算複雑性理論)とスティーブン・クック · 続きを見る »

複雑性クラス

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

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

計算モデル

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

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

計算複雑性理論

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

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

論理回路

論理回路(ろんりかいろ、logic circuit)は、論理演算を行う電気回路及び電子回路である。真理値の「真」と「偽」、あるいは二進法の「0」と「1」を、電圧の正負や高低、電流の方向や多少、位相の差異、パルスなどの時間の長短、などで表現し、論理素子などで論理演算を実装する。電圧の高低で表現する場合それぞれを「」「」等という。基本的な演算を実装する論理ゲートがあり、それらを組み合わせて複雑な動作をする回路を構成する。状態を持たない組み合わせ回路と状態を持つ順序回路に分けられる。論理演算の結果には、「真」、「偽」の他に「不定」がある。ラッチ回路のdon't care, フリップフロップ回路の禁止が相当する。 ここでの論理は離散(digital)であるためディジタル回路を用いる。論理演算を行うアナログ回路、「アナログ論理」を扱う回路(どちらも「アナログ論理回路」)もある。 多値論理回路も量子コンピュータで注目されている。 電気(電子)的でないもの(たとえば流体素子や光コンピューティングを参照)もある。 以下では離散なデジタル回路を扱う。.

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

L (計算複雑性理論)

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

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

NL (計算複雑性理論)

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

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

NP完全問題

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

新しい!!: NC (計算複雑性理論)とNP完全問題 · 続きを見る »

P (計算複雑性理論)

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

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

決定問題

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

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

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