ブラウザよりも高速アクセス！
74 関係: 加速定理、合成数、多項式時間、多項式時間変換、二分探索、二進法、形式体系、マヌエル・ブラム、チューリングマシン、ハミルトン閉路問題、ユリス・ハルトマニス、ランダウの記号、リチャード・カープ、リチャード・スターンズ、レスリー・ヴァリアント、ブラムの公理、ブール論理、アルゴリズム、アンドリュー・チーチー・ヤオ、アディ・シャミア、オペレーションズ・リサーチ、ギガ、クレイ数学研究所、グラフ同型、スティーブン・クック、スケーラビリティ、タンパク質構造予測、充足可能性問題、回路計算量、BPP (計算複雑性理論)、BQP、Co-NP、理論計算機科学、素因数分解、素数、素数判定、純粋数学、生物学、DSPACE、DTIME、EXPTIME、非決定性チューリングマシン、頂点被覆問題、複雑性、複雑性クラス、計算可能関数、計算可能性理論、計算モデル、計算理論、計算資源、...、計算機、計算機科学、記述計算量、論理回路、関数 (数学)、還元 (計算複雑性理論)、離散対数、集積回路、L (計算複雑性理論)、NC (計算複雑性理論)、NL (計算複雑性理論)、NP、NP完全問題、NP困難、NTIME、P (計算複雑性理論)、P≠NP予想、PSPACE、暗号理論、決定問題、指数関数時間、文字列、整数計画問題、2000年。 インデックスを展開 (24 もっと) »
加速定理
計算複雑性理論における加速定理（かそくていり、speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、より少ない資源しか使用しない算法）の存在を示す定理である。.
新しい！!: 計算複雑性理論と加速定理 · 続きを見る »
合成数
合成数（ごうせいすう、Composite number）は、自然数で、1とその数自身以外の約数を持つ数である。2つ以上の素数の積で表すことのできる自然数と定義してもよい。たとえば15は1と15自身以外に3と5を約数に持つ（または 3×5 と素数の積で表される）ので合成数である。9や25など素数を2乗した数は1つしか素因数をもたないが、9.
新しい！!: 計算複雑性理論と合成数 · 続きを見る »
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: 計算複雑性理論と多項式時間 · 続きを見る »
多項式時間変換
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。.
新しい！!: 計算複雑性理論と多項式時間変換 · 続きを見る »
二分探索
二分探索（にぶんたんさく、binary search、BS）や二分検索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。.
新しい！!: 計算複雑性理論と二分探索 · 続きを見る »
二進法
二進法（にしんほう）とは、2 を底（てい、基（base）とも）とし、底の冪の和で数を表現する方法である。 英語でバイナリ (binary) という。binaryという語には「二進法」の他に「二個一組」「二個単位」といったような語義もある（例: バイナリ空間分割）。.
新しい！!: 計算複雑性理論と二進法 · 続きを見る »
形式体系
形式体系（けいしきたいけい、Formal System）は、数学のモデルに基づいた任意の well-defined な抽象思考体系と定義される。エウクレイデスの『原論』は史上初の形式体系とされることが多く、形式体系の特徴をよく表している。その論理的基盤による体系の命題と帰結の関係（論理包含）は、他の抽象モデルを何らかの基盤とする体系から形式体系を区別するものである。形式体系は大きな理論や分野（例えばユークリッド幾何学）の基盤またはそのものとなることが多く、現代数学では証明論やモデル理論などと同義に扱われる。ただし形式体系は必ずしも数学的である必然性はなく、例えばスピノザの『エチカ』はエウクレイデスの『原論』の形式を模倣した哲学（倫理学）書である。 形式体系には形式言語があり、その形式言語は基本的な記号（シンボル）で構成される。形式言語の文（式）は公理群を出発点として、所定の構成規則（推論規則）に従って発展する。従って形式体系は基本的な記号群の有限の組み合わせを通して構築された任意個の数式で構成され、その組み合わせは公理群と構成規則群から作り出される。 数学における形式体系は以下の要素から構成される.
新しい！!: 計算複雑性理論と形式体系 · 続きを見る »
マヌエル・ブラム
マヌエル・ブラム（Manuel Blum、1938年4月26日 - ）はベネズエラのカラカス出身の著名な計算機科学者。1995年、「計算複雑性理論の基礎的研究とその暗号およびプログラム検証への応用に関する貢献に対して」チューリング賞を授与された。.
新しい！!: 計算複雑性理論とマヌエル・ブラム · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: 計算複雑性理論とチューリングマシン · 続きを見る »
ハミルトン閉路問題
ハミルトン閉路問題（ハミルトンへいろもんだい）とは、与えられたグラフについて、全ての頂点を一度だけ通る閉路が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者ウィリアム・ローワン・ハミルトンの名に因む。.
新しい！!: 計算複雑性理論とハミルトン閉路問題 · 続きを見る »
ユリス・ハルトマニス
ユリス・ハルトマニス（Juris Hartmanis、1928年7月7日 - ）は、著名な計算機科学者であり、計算理論を専門とする。1993年、リチャード・スターンズと共に「計算複雑性理論の分野を確立した独創的な論文に対して」チューリング賞を受賞した。.
新しい！!: 計算複雑性理論とユリス・ハルトマニス · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: 計算複雑性理論とランダウの記号 · 続きを見る »
リチャード・カープ
リチャード・マニング・カープ（Richard Manning Karp、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。.
新しい！!: 計算複雑性理論とリチャード・カープ · 続きを見る »
リチャード・スターンズ
リチャード・エドウィン・スターンズ（Richard Edwin Stearns, 1936年7月5日 - ）は、アメリカ合衆国の計算機科学者。1993年、ユリス・ハルトマニスと共に「計算複雑性理論の分野を確立した独創的な論文に対して」チューリング賞を受賞した。1994年、Association for Computing Machinery (ACM) のフェローに選ばれた。 1961年、プリンストン大学にての指導で博士号を得た。2006年現在、ニューヨーク州立大学オールバニ校計算機科学科の名誉教授を務めている。.
新しい！!: 計算複雑性理論とリチャード・スターンズ · 続きを見る »
レスリー・ヴァリアント
レスリー・ガブリエル・ヴァリアント（、1949年3月28日 - ）は、イギリスの計算機科学者で計算理論の専門家である。 理論計算機科学での業績でよく知られている。計算複雑性理論において様々な貢献をしており、#P完全性の記法を導入して、なぜ数え上げ問題が難しいのかを説明した。また、機械学習の「確率的で近似的に正しい」（、"probably approximately correct"）モデルを提唱して機械学習の理論的発展に貢献し、の概念も提唱した。初期にはオートマタ理論を研究し、CYK法を発展させたヴァリアントのアルゴリズムを考案。これは2010年現在も、文脈自由文法を判定する漸近的に最速なアルゴリズムである。計算論的神経科学の分野でも記憶と学習についての研究を行っている。 特に有名な論文として Vijay Vazirani と共同執筆した論文があり、UNIQUE-SAT ∈ P ⇒ NP.
新しい！!: 計算複雑性理論とレスリー・ヴァリアント · 続きを見る »
ブラムの公理
計算複雑性理論におけるブラムの公理（ブラムのこうり、Blum axioms）またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。 重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。.
新しい！!: 計算複雑性理論とブラムの公理 · 続きを見る »
ブール論理
ブール論理（ブールろんり、Boolean logic）は、古典論理のひとつで、その名称はブール代数ないしその形式化を示したジョージ・ブールに由来する。 リレーなどによる「スイッチング回路の理論」として1930年代に再発見され（論理回路#歴史を参照）、間もなくコンピュータに不可欠な理論として広まり、こんにちでは一般的に使われている。 本項目では、集合代数を用いて、集合、ブール演算、ベン図、真理値表などの基本的解説とブール論理の応用について解説する。ブール代数の記事ではブール論理の公理を満足する代数的構造の型を説明している。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。.
新しい！!: 計算複雑性理論とブール論理 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: 計算複雑性理論とアルゴリズム · 続きを見る »
アンドリュー・チーチー・ヤオ
アンドリュー・チーチー・ヤオ（Andrew Chi-Chih Yao、、1946年12月24日 - ）は、著名な計算機科学者にして計算理論家。ミニマックス法を用い今日「」として知られる理論を証明した。 中国上海に生まれた。国立台湾大学で物理学を学び、1972年にハーバード大学で物理学の博士号を取得した。1975年にはイリノイ大学アーバナ・シャンペーン校で計算機科学の博士号を取得している。 1996年、クヌース賞を受賞。2000年、「計算複雑性理論に基づく擬似乱数、暗号理論、通信複雑性などの計算理論への基本的貢献に対して」チューリング賞を授与された。 1982年から1986年までスタンフォード大学で正教授を務めた。1996年から2004年までプリンストン大学で工学と応用科学の教授を務め、アルゴリズムと複雑性の研究を続けた。2004年、中国北京の清華大学高等研究センター (CATSU) の教授となり、同大学理論計算機科学研究センター (ITCS) のセンター長となった。香港中文大学でも教授を務めている。現在は中華人民共和国籍を取得している。 米国科学アカデミーの会員、アメリカ芸術科学アカデミーのフェロー、アメリカ科学振興協会のフェローなども務めている。中国科学院の院士。妻のも理論計算機科学の研究者として知られている。.
新しい！!: 計算複雑性理論とアンドリュー・チーチー・ヤオ · 続きを見る »
アディ・シャミア
アディ・シャミア（Adi Shamir、עדי שמיר、1952年7月6日 - ）は、イスラエルの暗号の研究者。ロナルド・リベスト、レオナルド・エーデルマンとともにRSA暗号を発明したことで知られる。また、ゼロ知識証明のでも知られ、暗号理論と計算機科学に様々な貢献をしてきた。.
新しい！!: 計算複雑性理論とアディ・シャミア · 続きを見る »
オペレーションズ・リサーチ
ペレーションズ・リサーチ（英語：operations research、米）、オペレーショナル・リサーチ（英語：operational research、英、略称：OR）は、数学的・統計的モデル、アルゴリズムの利用などによって、さまざまな計画に際して最も効率的になるよう決定する科学的技法である。.
新しい！!: 計算複雑性理論とオペレーションズ・リサーチ · 続きを見る »
ギガ
（giga, 記号:G）は国際単位系 (SI) における接頭辞の1つで、基礎となる単位の109（＝十億）倍の量であることを示す。 1960年に定められたもので、ギリシャ語で「巨人」を意味する γίγας (gigas) に由来する。 コンピュータの分野においては、ギガは1,073,741,824 (230) を表す場合もある（ギガビット、ギガバイトなど）。しかし、1,000,000,000 (109) を表す場合もある（例:1ギガビット/秒 (Gbps) ＝1,000,000,000ビット/秒）。曖昧さを回避するために230については2進接頭辞「ギビ」(gibi, 記号:Gi) が導入されたが、あまり用いられていない。 英語圏（特にアメリカ）では、ギガは"gig"と略されることが多い。"giga"の通常の英語発音は「ギガ」であるが、まれに「ジガ」と発音されることもある。「バック・トゥ・ザ・フューチャーシリーズ」では、"giga"が登場人物たちの会話に登場するが、英語の音声は「ジガ」であるところ（英語としても少数派の発音）、日本語の翻訳では「ジゴ」と間違えていたことが知られている。.
新しい！!: 計算複雑性理論とギガ · 続きを見る »
クレイ数学研究所
レイ数学研究所（クレイすうがくけんきゅうじょ、Clay Mathematics Institute、略称 CMI）は、アメリカ合衆国マサチューセッツ州ケンブリッジに建設された個人的・非営利な施設であり、数学の発展とそれを広めることを目的としている。この研究所は、有望な数学者たちへ様々な賞や賞金を与えている。CMI は、1998年、ハーバード大学の数学者アーサー・ジェイフと、建設の際に投資を行った実業家ランドン・T・クレイによって建設された。.
新しい！!: 計算複雑性理論とクレイ数学研究所 · 続きを見る »
グラフ同型
ラフ同型（ぐらふどうけい）とはグラフ理論における概念の一つである。.
新しい！!: 計算複雑性理論とグラフ同型 · 続きを見る »
スティーブン・クック
ティーブン・クック（Stephen A. Cook, 1939年12月14日 - ）は、米国・カナダの計算機科学者・数学者。専門は計算理論、特に計算複雑性理論の論理学的側面やの研究に従事している。2012年現在、トロント大学計算機科学科と数学科の教授である。.
新しい！!: 計算複雑性理論とスティーブン・クック · 続きを見る »
スケーラビリティ
ーラビリティ（scalability）とは利用者や仕事の増大に適応できる能力・度合いのこと。電気通信やソフトウェア工学において、システムまたはネットワークまたはアルゴリズムの、持つべき望ましい特性の1つで、一種の拡張性である。より具体的には、小規模なシステムを大規模にする場合に、システム全体を交換する方法（建物で例えると大きな物件に引っ越すこと）では無く、リソース（特にハードウェア）の追加によって大規模なものへと透過的に規模拡張できる能力（建物で例えると、増築や別棟を建てること）はスケーラビリティの一種だといえる。リソースの量に比例して全体のスループットが向上するシステムはスケーラブルな（scalable）システムまたはスケーラビリティのあるシステムと呼ばれる。 システムの特性としてのスケーラビリティに一般的な定義を与えるのは難しい。具体的な事例においては、問題としている領域でスケーラビリティを確保するための条件を特定することが必要である。これはデータベース、ルータ、ネットワークなど情報工学の分野において非常に重要なことである。スケーラビリティは分散処理の'''透過性'''の概念と密接なつながりがある。 スケーラビリティの高さは様々な尺度で評価される。例として;規模透過性;位置透過性;異種透過性 がある。スケーラビリティについて議論する際には規模透過性のみを問題にすることも多い。 例えば、スケーラブルなデータベース管理システムではプロセッサやストレージを追加することでより多くのトランザクションを処理できるようにアップグレードでき、またアップグレードをシャットダウンなしに実行できる。 ルーティングプロトコルがネットワークの規模に関してスケーラブルであると言われるのは、Nをネットワーク内のノード数としたときに、各ノードに必要なルーティングテーブルのサイズが O(log N) に従って増大するときである。.
新しい！!: 計算複雑性理論とスケーラビリティ · 続きを見る »
タンパク質構造予測
タンパク質構造予測 （たんぱくしつこうぞうよそく） は、タンパク質についてそのアミノ酸配列をもとに3次元構造（立体配座）を予測することをいい、バイオインフォマティクスおよび計算化学における研究分野の一つである。専門的な言葉では「タンパク質の一次構造をもとに三次構造を予測すること」と表現できる。タンパク質のアミノ酸配列は一次構造と呼ばれる。タンパク質のアミノ酸配列は、その遺伝子が記録されたDNAの塩基配列から、遺伝コード（コドン）の対応表に基づいて、導出することができる。生体内において、ほとんどのタンパク質の一次構造は一意的に3次元構造（三次構造、コンフォメーション）をとる（タンパク質が折りたたまれる）。タンパク質の3次元構造を知ることは、そのタンパク質の機能を理解する上で有力な手がかりとなる。 創薬などのように公益性が高いさまざまな分野において応用されている。 タンパク質の3次元構造を解明する手段としては、実験による方法と予測による方法がある。この項目では予測による方法を説明する。 タンパク質構造予測においては多くの手法が考案されている。それぞれの手法の有効性は、2年ごとにCASP（Critical Assessment of Techniques for Protein Structure Prediction）により、評価されている。.
新しい！!: 計算複雑性理論とタンパク質構造予測 · 続きを見る »
充足可能性問題
充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい！!: 計算複雑性理論と充足可能性問題 · 続きを見る »
回路計算量
回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。.
新しい！!: 計算複雑性理論と回路計算量 · 続きを見る »
BPP (計算複雑性理論)
計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。.
新しい！!: 計算複雑性理論とBPP (計算複雑性理論) · 続きを見る »
BQP
計算複雑性理論において、BQPとは、量子コンピュータによって誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Quantum Polynomial time の頭文字をとったものである。ある問題がBQPに属すなら、高い確率で正答を返し、多項式時間で実行可能な、量子コンピュータのためのアルゴリズムが存在する。そのアルゴリズムは解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 '''BPP'''と同じように、定義の1/3というのは0以上1/2未満の任意の定数である。その定数が変化してもBQPは変化しない。.
新しい！!: 計算複雑性理論とBQP · 続きを見る »
Co-NP
co-NPとは計算量理論における問題クラスの一つである。.
新しい！!: 計算複雑性理論とCo-NP · 続きを見る »
理論計算機科学
論計算機科学（りろんけいさんきかがく、英語：theoretical computer science）は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、現実のコンピュータを扱うことも多いが、チューリングマシンなどの計算モデルを扱うことも多い。 理論計算機科学の代表的な分野として以下のものがある。.
新しい！!: 計算複雑性理論と理論計算機科学 · 続きを見る »
素因数分解
素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。.
新しい！!: 計算複雑性理論と素因数分解 · 続きを見る »
素数
素数（そすう、prime number）とは、 より大きい自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。 一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 \mathbb Z での素数は有理素数（ゆうりそすう、rational prime）と呼ばれることもある。 最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。 素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。 自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。 分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ。.
新しい！!: 計算複雑性理論と素数 · 続きを見る »
素数判定
素数判定（そすうはんてい）とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。.
新しい！!: 計算複雑性理論と素数判定 · 続きを見る »
純粋数学
純粋数学（じゅんすいすうがく、pure mathematics）とは、しばしば応用数学と対になる概念として、応用をあまり意識しない数学の分野に対して用いられる総称である。 数学のどの分野が純粋数学でありどの分野が応用数学であるかという社会的に広く受け入れられた厳密な合意があるわけではなく、区別は便宜的なものとして用いられることが多い。また数学がより広範な範囲で利用されるに従い、分野としての純粋と応用との区別はあいまいで困難なものとなってきている。ただし、純粋数学という用語を用いる場合の志向としては、議論される数学の厳密性、抽象性を基とした数学単体での美しさを重視する傾向がある。.
新しい！!: 計算複雑性理論と純粋数学 · 続きを見る »
生物学
生物学（せいぶつがく、、biologia）とは、生命現象を研究する、自然科学の一分野である。 広義には医学や農学など応用科学・総合科学も含み、狭義には基礎科学（理学）の部分を指す。一般的には後者の意味で用いられることが多い。 類義語として生命科学や生物科学がある（後述の#「生物学」と「生命科学」参照）。.
新しい！!: 計算複雑性理論と生物学 · 続きを見る »
DSPACE
DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース（プログラムの実行に必要な物理的メモリ量）と直接対応することから、最もよく研究されている複雑性の尺度の1つである。.
新しい！!: 計算複雑性理論とDSPACE · 続きを見る »
DTIME
DTIME（またはTIME）は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量（ステップ数）を表す。実際のリソース（プログラムの実行にかかる時間）と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 n の問題を解くのに O(f(n)) の計算時間がかかる場合、その複雑性クラスは \text(f(n))（または \text(f(n))）となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。.
新しい！!: 計算複雑性理論とDTIME · 続きを見る »
EXPTIME
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。 DTIMEでは次のように表される。 以下の関係が知られている。 また、時間階層定理と領域階層定理により、次のようになる。 従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P.
新しい！!: 計算複雑性理論とEXPTIME · 続きを見る »
非決定性チューリングマシン
非決定性チューリング機械（ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。.
新しい！!: 計算複雑性理論と非決定性チューリングマシン · 続きを見る »
頂点被覆問題
頂点被覆問題（ちょうてんひふくもんだい）は計算複雑性理論における問題の一つであり、 NP完全に属する問題の内のひとつ。.
新しい！!: 計算複雑性理論と頂点被覆問題 · 続きを見る »
複雑性
複雑性（ふくざつせい、complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.
新しい！!: 計算複雑性理論と複雑性 · 続きを見る »
複雑性クラス
複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.
新しい！!: 計算複雑性理論と複雑性クラス · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: 計算複雑性理論と計算可能関数 · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: 計算複雑性理論と計算可能性理論 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: 計算複雑性理論と計算モデル · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: 計算複雑性理論と計算理論 · 続きを見る »
計算資源
計算資源（けいさんしげん、英語: computational resource）とは、コンピュータ科学などで、計算機（具体的なコンピュータ、そこで動くプロセスやジョブ、あるいは抽象的な計算模型）が「計算量」のために費す、具体的あるいは抽象的な「資源」である。計算機資源と言うこともあるが、その場合はプロセッサ時間や記憶装置などコンピュータのハードウェアの占有量のような具体的なものを指していることが多い。 その他に、アプリケーションプログラムの設定データのような情報をデスクトップ環境などのシステムが保存しているものを「リソース」と呼ぶことがある。詳細は、最後の#その他の節のリンク先を参照のこと。.
新しい！!: 計算複雑性理論と計算資源 · 続きを見る »
計算機
計算機（けいさんき）は、計算を機械的に、さらには自動的に行う装置である。人間が行う計算を援助するのみのものや、手動操作で自動的ではないものなどは計算器という文字表現をすることがある。.
新しい！!: 計算複雑性理論と計算機 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: 計算複雑性理論と計算機科学 · 続きを見る »
記述計算量
記述計算量（きじゅつけいさんりょう、Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、'''PH'''は二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。.
新しい！!: 計算複雑性理論と記述計算量 · 続きを見る »
論理回路
論理回路（ろんりかいろ、logic circuit）は、論理演算を行う電気回路及び電子回路である。真理値の「真」と「偽」、あるいは二進法の「0」と「1」を、電圧の正負や高低、電流の方向や多少、位相の差異、パルスなどの時間の長短、などで表現し、論理素子などで論理演算を実装する。電圧の高低で表現する場合それぞれを「」「」等という。基本的な演算を実装する論理ゲートがあり、それらを組み合わせて複雑な動作をする回路を構成する。状態を持たない組み合わせ回路と状態を持つ順序回路に分けられる。論理演算の結果には、「真」、「偽」の他に「不定」がある。ラッチ回路のdon't care, フリップフロップ回路の禁止が相当する。 ここでの論理は離散(digital)であるためディジタル回路を用いる。論理演算を行うアナログ回路、「アナログ論理」を扱う回路（どちらも「アナログ論理回路」）もある。 多値論理回路も量子コンピュータで注目されている。 電気（電子）的でないもの（たとえば流体素子や光コンピューティングを参照）もある。 以下では離散なデジタル回路を扱う。.
新しい！!: 計算複雑性理論と論理回路 · 続きを見る »
関数 (数学)
数学における関数（かんすう、、、、、函数とも）とは、かつては、ある変数に依存して決まる値あるいはその対応を表す式の事であった。この言葉はライプニッツによって導入された。その後定義が一般化されて行き、現代的には数の集合に値をとる写像の一種であると理解される。.
新しい！!: 計算複雑性理論と関数 (数学) · 続きを見る »
還元 (計算複雑性理論)
還元（かんげん、Reduction）とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。 直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。.
新しい！!: 計算複雑性理論と還元 (計算複雑性理論) · 続きを見る »
離散対数
代数学における離散対数（りさんたいすう、discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解(en:integer factorization)と以下の点が共通している：.
新しい！!: 計算複雑性理論と離散対数 · 続きを見る »
集積回路
SOPパッケージに封入された標準ロジックICの例 集積回路（しゅうせきかいろ、integrated circuit, IC）は、主としてシリコン単結晶などによる「半導体チップ」の表面および内部に、不純物の拡散による半導体トランジスタとして動作する構造や、アルミ蒸着とエッチングによる配線などで、複雑な機能を果たす電子回路の多数の素子が作り込まれている電子部品である。多くの場合、複数の端子を持つ比較的小型のパッケージに封入され、内部で端子からチップに配線されモールドされた状態で、部品・製品となっている。.
新しい！!: 計算複雑性理論と集積回路 · 続きを見る »
L (計算複雑性理論)
計算量理論において、Lとは、決定性チューリングマシンで対数規模の領域（メモリ）を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。 Lと関連する計算量に'''NL'''がある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、\mathrm \subseteq \mathrm が成り立つ。 また、O(log n) の領域を使用する決定機械は時間 2O(log n).
新しい！!: 計算複雑性理論とL (計算複雑性理論) · 続きを見る »
NC (計算複雑性理論)
計算複雑性理論において、NC（Nick's Class）とは多項式個数のプロセッサで構成される並列計算機で，問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(nk)個の並列プロセッサを使って O((log n)c) の時間で解ける（c と k は定数）。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。 クラス P と同様、NC に属する問題は並列計算機で効率的に解くことができると見なされている。並列計算機は通常の計算機でシミュレート可能であるため、NC は P に含まれる。NC.
新しい！!: 計算複雑性理論とNC (計算複雑性理論) · 続きを見る »
NL (計算複雑性理論)
NL（えぬえる、Nondeterministic Logarithmic-space）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL.
新しい！!: 計算複雑性理論とNL (計算複雑性理論) · 続きを見る »
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。.
新しい！!: 計算複雑性理論とNP · 続きを見る »
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完全問題 · 続きを見る »
NP困難
NP完全、'''NP困難'''の相関を表すベン図 NP困難（エヌピーこんなん、NP-hard）とは計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」ことである。正確にいうと問題 H がNP困難であるとは、「NPに属する任意の問題 L が H へ帰着可能である」と定義される。この「帰着」の定義として何を用いるかにより微妙に定義が異なることになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。NP困難問題を解ける多項式時間の機械がもしあれば、それを利用してNPに属するどの問題も多項式時間で解くことができる。 NP完全問題とは、NP困難であり、かつNPに属する問題である。これと異なり、NP困難である問題はNPに属するとは限らない。NPは決定問題のクラスなのでNP完全もまた決定問題に限られるが、定義に用いる帰着の種類によってはNP困難には決定問題、探索問題(en)、組合せ最適化問題など様々な問題が属しうる。 上に挙げた定義から、問題 H がNP困難なとき次のことが言える（以下は定義ではなく主張）。.
新しい！!: 計算複雑性理論とNP困難 · 続きを見る »
NTIME
NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。 よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。 同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性時間階層定理によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。 Category:計算複雑性理論 Category:数学に関する記事.
新しい！!: 計算複雑性理論とNTIME · 続きを見る »
P (計算複雑性理論)
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。.
新しい！!: 計算複雑性理論とP (計算複雑性理論) · 続きを見る »
P≠NP予想
P≠NP予想（P≠NPよそう、）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。P対NP問題（PたいNPもんだい、）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。.
新しい！!: 計算複雑性理論とP≠NP予想 · 続きを見る »
PSPACE
PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。.
新しい！!: 計算複雑性理論とPSPACE · 続きを見る »
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
新しい！!: 計算複雑性理論と暗号理論 · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: 計算複雑性理論と決定問題 · 続きを見る »
指数関数時間
指数関数時間（しすうかんすうじかん）あるいは指数時間（しすうじかん）とは、計算理論において指数関数を用いてあらわされる計算時間。計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。 一般に指数関数時間やその以上のアルゴリズムは時間がかかりすぎるので実用には適さない。そのようなアルゴリズムは特殊な場合にしか使われない。.
新しい！!: 計算複雑性理論と指数関数時間 · 続きを見る »
文字列
文字列（もじれつ）は、単語や文章のような、文字の連なったもの。ストリング (string)、テキスト (text) という場合もある。コンピュータ、特にプログラミングの分野で用いることが多い。.
新しい！!: 計算複雑性理論と文字列 · 続きを見る »
整数計画問題
整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。.
新しい！!: 計算複雑性理論と整数計画問題 · 続きを見る »
2000年
400年ぶりの世紀末閏年（20世紀および2千年紀最後の年）である100で割り切れるが、400でも割り切れる年であるため、閏年のままとなる（グレゴリオ暦の規定による）。。Y2Kと表記されることもある（“Year 2000 ”の略。“2000”を“2K ”で表す）。また、ミレニアムとも呼ばれる。 この項目では、国際的な視点に基づいた2000年について記載する。.
新しい！!: 計算複雑性理論と2000年 · 続きを見る »
