11 関係: 多項式時間、グラフ理論、シュプリンガー・ジャパン、写像、全単射、BPP (計算複雑性理論)、Co-NP、量子コンピュータ、NP、NP完全問題、P (計算複雑性理論)。
多項式時間
多項式時間(たこうしきじかん)とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい!!: グラフ同型と多項式時間 · 続きを見る »
グラフ理論
ラフ理論(グラフりろん、graph theory)は、ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい!!: グラフ同型とグラフ理論 · 続きを見る »
シュプリンガー・ジャパン
ュプリンガー・ジャパン(しゅぷりんがー・じゃぱん・Springer Japan)は、ドイツのSTM(科学・技術・医学)出版社であるシュプリンガー・サイエンス・アンド・ビジネス・メディアの日本法人である。この親会社が出版する書籍・ジャーナルを日本国内で出版している。 同社は、以前にはそれらの日本語翻訳書や和書の出版も行っていたが、2012年に権利を丸善へと譲渡して和書事業から撤退した。これに拠って、シュプリンガー・ジャパンから出版されていた和書は丸善から順次(再)刊行されている。 2015年5月、シュプリンガー・サイエンス+ビジネスメディアとマクミラン・サイエンス・アンド・エデュケーションの大半の事業の合併が、欧州連合や米国司法省などの主要な公正競争監視機関により承認された。新会社の名称は「シュプリンガー・ネイチャー(Springer Nature)」。.
新しい!!: グラフ同型とシュプリンガー・ジャパン · 続きを見る »
写像
写像(しゃぞう、mapping, map)とは、二つの集合が与えられたときに、一方の集合の各元に対し、他方の集合のただひとつの元を指定して結びつける対応のことである。函数(関数)、変換、作用素、射などが写像の同義語として用いられることもある。 ブルバキに見られるように、写像は集合とともに現代数学の基礎となる道具の一つである。現代的な立場では、「写像」と(一価の)「函数」は論理的におなじ概念を表すものと理解されているが、歴史的には「函数」の語は解析学に出自を持つものであり、一部には必ずしも写像でないものも函数の名の下におなじ範疇に扱われる(多価函数参照)。文献によっては「数の集合(大抵の場合実数体 または複素数体 の部分集合)を終域に持つ写像」をして特に「函数」と呼び、「写像」はより一般の場合に用いる。函数、二項関係、対応の各項も参照のこと。.
全単射
数学において、全単射(ぜんたんしゃ)あるいは双射(そうしゃ)(bijective function, bijection) とは、写像であって、その写像の終域となる集合の任意の元に対し、その元を写像の像とする元が、写像の定義域となる集合に常にただ一つだけ存在するようなもの、すなわち単射かつ全射であるような写像のことを言う。例としては、群論で扱われる置換が全単射の良い例である。 全単射であることを一対一上への写像 (one-to-one onto mapping)あるいは一対一対応 (one-to-one correspondence) ともいうが、紛らわしいのでここでは使用しない。 写像 f が全単射のとき、fは可逆であるともいう。.
BPP (計算複雑性理論)
計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。.
新しい!!: グラフ同型とBPP (計算複雑性理論) · 続きを見る »
Co-NP
co-NPとは計算量理論における問題クラスの一つである。.
新しい!!: グラフ同型とCo-NP · 続きを見る »
量子コンピュータ
量子コンピュータ (りょうしコンピュータ、英語:quantum computer) は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ(以下「古典コンピュータ」)の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下)で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.
新しい!!: グラフ同型と量子コンピュータ · 続きを見る »
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time(非決定性多項式時間)の略である(「Non-P」ないしは「Not-P」ではない)。.
NP完全問題
NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック(Stephen Cook (1971).
新しい!!: グラフ同型とNP完全問題 · 続きを見る »
P (計算複雑性理論)
計算量理論におけるPとは多項式時間(polynomial time)で解ける判定問題の集合である。.
新しい!!: グラフ同型とP (計算複雑性理論) · 続きを見る »