ブラウザよりも高速アクセス！
55 関係: AKS素数判定法、多項式、多項式階層、多項式時間、多項式時間変換、上界、一方向性関数、予想、ミレニアム懸賞問題、マニンドラ・アグラワル、チューリングマシン、ハッシュ関数、ユリス・ハルトマニス、ドナルド・クヌース、クルト・ゲーデル、クレイ数学研究所、クヌースの矢印表記、グラフ同型、ゲーデル賞、ゲオルク・カントール、ジョン・ナッシュ、ジョン・フォン・ノイマン、スティーブン・クック、公開鍵暗号、充足可能性問題、回路計算量、Co-NP、理論計算機科学、神託機械、素因数分解、素数、素数判定、ElGamal暗号、計算複雑性理論、計算量的安全性を持つ暗号、計算機科学の未解決問題、自然な証明、自然数、離散対数、NP、NP完全問題、P (計算複雑性理論)、RSA暗号、ZFC、暗号理論、暗号解読、楕円曲線暗号、正当性 (計算機科学)、決定問題、決定的アルゴリズム、...、擬似乱数、懸賞金、懸賞金問題、数学上の未解決問題、2000年。 インデックスを展開 (5 もっと) »
AKS素数判定法
AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 n が素数であるかどうかを判定するのにかかる時間が\log(n) の多項式を上界とすることをいう。n の多項式ではないことに注意する必要がある。 AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。 この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。 素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。.
新しい！!: P≠NP予想とAKS素数判定法 · 続きを見る »
多項式
数学における多項式（たこうしき、poly­nomial）は、多数を意味するpoly- と部分を意味する -nomen あるいは nomós を併せた語で、定数および不定元（略式ではしばしば変数と呼ぶ）の和と積のみからなり、代数学の重要な対象となる数学的対象である。歴史的にも現代代数学の成立に大きな役割を果たした。 不定元がひとつの多項式は、一元多項式あるいは一変数多項式 と呼ばれ、不定元を とすれば のような形をしている。各部分 "", "", "", "" のことを項（こう、）と呼ぶ。一つの項だけからできている式を単項式 (monomial)、同様に二項式 (binomial)、三項式 (trinomial) などが、-nomial にラテン配分数詞を付けて呼ばれる。すなわち、多項式とは「多数」の「項」を持つものである。単項式の語が頻出であることに比べれば、二項式の語の使用はやや稀、三項式あるいはそれ以上の項数に対する語の使用はごく稀で一口に多項式として扱う傾向があり、それゆえ単項式のみ多項式から排他的に分類するものもある。また多項式のことを整式 (integral expression) と呼ぶ流儀もある。 多項式同士の等式として与えられる方程式は多項式方程式と呼ばれ、特に有理数係数の場合において代数方程式という。多項式方程式は多項式函数の零点を記述するものである。 不定元がふたつならば二元 (bivariate), 三つならば三元 (trivariate) というように異なるアリティを持つ多元多項式が同様に定義できる。算術あるいは初等代数学において、数の計算の抽象化として実数（あるいは必要に応じてより狭く有理数、整数、自然数）を代表する記号としての「文字」変数を伴う「」およびその計算を扱うが、それは大抵の場合多変数の多項式である。 本項では主として一元多項式を扱い、多元の場合にも多少触れるが、詳細は多元多項式の項へ譲る。.
新しい！!: P≠NP予想と多項式 · 続きを見る »
多項式階層
多項式階層（たこうしきかいそう、Polynomial hierarchy）は、計算量理論における計算量の階層であり、神託機械を使って '''P'''、NP、co-'''NP''' を一般化させて定義されるものである。.
新しい！!: P≠NP予想と多項式階層 · 続きを見る »
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: P≠NP予想と多項式時間 · 続きを見る »
多項式時間変換
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。.
新しい！!: P≠NP予想と多項式時間変換 · 続きを見る »
上界
上界（じょうかい）.
一方向性関数
一方向性関数（いちほうこうせいかんすう、one-way function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。 下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。.
新しい！!: P≠NP予想と一方向性関数 · 続きを見る »
予想
予想（よそう、expectation, forecast, conjecture）とは、.
ミレニアム懸賞問題
ミレニアム懸賞問題（ミレニアムけんしょうもんだい、）とは、アメリカのクレイ数学研究所によって2000年に発表された100万ドルの懸賞金がかけられている7つの問題のことである。そのうち1つは解決済み、6つは2015年8月末の時点で未解決である。ミレニアム賞問題、ミレニアム問題とも呼ばれる。.
新しい！!: P≠NP予想とミレニアム懸賞問題 · 続きを見る »
マニンドラ・アグラワル
マニンドラ・アグラワル（Manindra Agrawal、1966年5月20日・カーンプル - ）は、インド工科大学カーンプル校の計算機科学、工学、Dean of Faculty Affairsの教授。 自らの生徒であったニラジュ・カヤル、ナイティン・サクセナとともに素数問題の計算量について研究し、AKS素数判定法を構成し、それを用いて素数問題がPに属することを示した。 その業績を評価され2002年にクレイ研究賞、2006年にゲーデル賞とファルカーソン賞を受賞。.
新しい！!: P≠NP予想とマニンドラ・アグラワル · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: P≠NP予想とチューリングマシン · 続きを見る »
ハッシュ関数
ハッシュ関数で名前と0から15までの整数をマッピングしている。"John Smith" と "Sandra Dee" のハッシュ値が衝突している点に注意。 ハッシュ関数 (ハッシュかんすう、hash function) あるいは要約関数とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。 ハッシュ関数は主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。 ハッシュ関数の入力を「キー (key)」と呼ぶ。ハッシュ関数は2つ以上のキーに同じハッシュ値をマッピングすることがある。多くの場合、このような衝突の発生は最小限に抑えるのが望ましい。したがって、ハッシュ関数はキーとハッシュ値をマッピングする際に可能な限り一様になるようにしなければならない。用途によっては、他の特性も要求されることがある。ハッシュ関数の考え方は1950年代に遡るが、ハッシュ関数の設計の改善は今でも盛んに研究されている。 ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、誤り訂正符号、暗号学的ハッシュ関数などと関係がある。これらの概念は一部はオーバーラップしているが、それぞれ用途が異なり、異なった形で設計・最適化されている。 またプログラミング言語の一部（Perl、Ruby等、主に高等言語とされる一般的なプログラミング言語の多く）においては、連想配列のことを伝統的にハッシュと呼ぶが、これは連想配列そのもののプログラムの内部的実装に拠るものであり、ハッシュ関数そのものとは全く異なる。連想配列はハッシュ関数の応用例の一つのハッシュテーブルの実用例である。.
新しい！!: P≠NP予想とハッシュ関数 · 続きを見る »
ユリス・ハルトマニス
ユリス・ハルトマニス（Juris Hartmanis、1928年7月7日 - ）は、著名な計算機科学者であり、計算理論を専門とする。1993年、リチャード・スターンズと共に「計算複雑性理論の分野を確立した独創的な論文に対して」チューリング賞を受賞した。.
新しい！!: P≠NP予想とユリス・ハルトマニス · 続きを見る »
ドナルド・クヌース
ドナルド・エルビン・クヌース（Donald Ervin Knuth, 1938年1月10日 -）は数学者、計算機科学者。スタンフォード大学名誉教授。 クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。 理論計算機科学への貢献とは別に、コンピュータによる組版システム TeX とフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。 作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。.
新しい！!: P≠NP予想とドナルド・クヌース · 続きを見る »
クルト・ゲーデル
ルト・ゲーデル（Kurt Gödel, 1906年4月28日 - 1978年1月14日）は、オーストリア・ハンガリー二重帝国（現チェコ）のブルノ生まれの数学者・論理学者である。業績には、完全性定理及び不完全性定理、連続体仮説に関する研究が知られる。.
新しい！!: P≠NP予想とクルト・ゲーデル · 続きを見る »
クレイ数学研究所
レイ数学研究所（クレイすうがくけんきゅうじょ、Clay Mathematics Institute、略称 CMI）は、アメリカ合衆国マサチューセッツ州ケンブリッジに建設された個人的・非営利な施設であり、数学の発展とそれを広めることを目的としている。この研究所は、有望な数学者たちへ様々な賞や賞金を与えている。CMI は、1998年、ハーバード大学の数学者アーサー・ジェイフと、建設の際に投資を行った実業家ランドン・T・クレイによって建設された。.
新しい！!: P≠NP予想とクレイ数学研究所 · 続きを見る »
クヌースの矢印表記
ヌースの矢印表記とは、1976年にドナルド・クヌースが巨大数を表現するために発明した表記法である。これは、乗算が加算の反復であり、冪乗が乗算の反復であるのと同様の考え方に基づくもので、冪乗の反復（テトレーション、超指数）を表す演算の表記法である。また、クヌースの矢印表記を拡張した表記法に、コンウェイのチェーン表記やBEAFがある。.
新しい！!: P≠NP予想とクヌースの矢印表記 · 続きを見る »
グラフ同型
ラフ同型（ぐらふどうけい）とはグラフ理論における概念の一つである。.
新しい！!: P≠NP予想とグラフ同型 · 続きを見る »
ゲーデル賞
ーデル賞 (Gödel Prize) は、理論計算機科学分野で優れた功績を残した人に、ACM（国際計算機学会）のアルゴリズムと計算量理論に関する部会とEATCS（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞金5,000ドルが贈られる。論理学者クルト・ゲーデルに由来する。計算機科学分野ではチューリング賞と並んで権威を持つ賞である。.
新しい！!: P≠NP予想とゲーデル賞 · 続きを見る »
ゲオルク・カントール
ルク・カントール ゲオルク・フェルディナント・ルートヴィッヒ・フィリップ・カントール（Georg Ferdinand Ludwig Philipp Cantor, 1845年3月3日 - 1918年1月6日）は、ドイツで活躍した数学者。.
新しい！!: P≠NP予想とゲオルク・カントール · 続きを見る »
ジョン・ナッシュ
ョン・フォーブス・ナッシュ・ジュニア（John Forbes Nash, Jr. 1928年6月13日 - 2015年5月23日 ）は、アメリカ人の数学者。専門分野は微分幾何学でありリーマン多様体の研究に関して大きな功績を残している。なお、彼の証明したナッシュ均衡が非常に有名であるため、ゲーム理論がナッシュのライフワークと思われていることもあるが、ナッシュがゲーム理論の研究に従事していたのは博士課程在学中とその後のわずか数年間だけである。 1994年にゲーム理論の経済学への応用に関する貢献によりラインハルト・ゼルテン、ジョン・ハーサニと共にノーベル経済学賞を、2015年に非線形偏微分方程式論とその幾何解析への応用に関する貢献によりルイス・ニーレンバーグと共にアーベル賞を受賞した。 ハリウッド映画『ビューティフル・マインド』は、彼の天才数学者としての偉業と成功、及び後の統合失調症に苦しむ人生を描いた作品であり、この面でも世間での彼の知名度は高い。.
新しい！!: P≠NP予想とジョン・ナッシュ · 続きを見る »
ジョン・フォン・ノイマン
ョン・フォン・ノイマン（ハンガリー名：Neumann János（ナイマン・ヤーノシュ、）、ドイツ名：ヨハネス・ルートヴィヒ・フォン・ノイマン、John von Neumann, Margittai Neumann János Lajos, Johannes Ludwig von Neumann, 1903年12月28日 - 1957年2月8日）はハンガリー出身のアメリカ合衆国の数学者。20世紀科学史における最重要人物の一人。数学・物理学・工学・計算機科学・経済学・気象学・心理学・政治学に影響を与えた。第二次世界大戦中の原子爆弾開発や、その後の核政策への関与でも知られる。.
新しい！!: P≠NP予想とジョン・フォン・ノイマン · 続きを見る »
スティーブン・クック
ティーブン・クック（Stephen A. Cook, 1939年12月14日 - ）は、米国・カナダの計算機科学者・数学者。専門は計算理論、特に計算複雑性理論の論理学的側面やの研究に従事している。2012年現在、トロント大学計算機科学科と数学科の教授である。.
新しい！!: P≠NP予想とスティーブン・クック · 続きを見る »
公開鍵暗号
公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開すらできるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。.
新しい！!: P≠NP予想と公開鍵暗号 · 続きを見る »
充足可能性問題
充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。.
新しい！!: P≠NP予想と充足可能性問題 · 続きを見る »
回路計算量
回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。.
新しい！!: P≠NP予想と回路計算量 · 続きを見る »
Co-NP
co-NPとは計算量理論における問題クラスの一つである。.
新しい！!: P≠NP予想とCo-NP · 続きを見る »
理論計算機科学
論計算機科学（りろんけいさんきかがく、英語：theoretical computer science）は計算機を理論的に研究する学問で、計算機科学の一分野である。計算機を数理モデル化して数学的に研究することを特徴としている。「数学的」という言葉は広義には公理的に扱えるもの全てを指すので、理論計算機科学は広義の数学の一分野でもある。理論計算機科学では、現実のコンピュータを扱うことも多いが、チューリングマシンなどの計算モデルを扱うことも多い。 理論計算機科学の代表的な分野として以下のものがある。.
新しい！!: P≠NP予想と理論計算機科学 · 続きを見る »
神託機械
託機械（しんたくきかい、oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。.
新しい！!: P≠NP予想と神託機械 · 続きを見る »
素因数分解
素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。.
新しい！!: P≠NP予想と素因数分解 · 続きを見る »
素数
素数（そすう、prime number）とは、 より大きい自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。 一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 \mathbb Z での素数は有理素数（ゆうりそすう、rational prime）と呼ばれることもある。 最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。 素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。 自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。 分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ。.
素数判定
素数判定（そすうはんてい）とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。.
新しい！!: P≠NP予想と素数判定 · 続きを見る »
ElGamal暗号
ElGamal暗号（エルガマルあんごう、ElGamal encryption）とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。1984年Taher Elgamalが発表した。.
新しい！!: P≠NP予想とElGamal暗号 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: P≠NP予想と計算複雑性理論 · 続きを見る »
計算量的安全性を持つ暗号
暗号理論において、計算量的安全性（けいさんりょうてきあんぜんせい）とは、暗号解読に必要なアルゴリズムの計算量に着目した暗号の安全性に関する概念の一つである。 具体的には、ある暗号を解読するための計算量が多項式時間に収まらない場合、その暗号は計算量的に安全という。実際に製品に組み込まれている暗号では鍵長などのパラメータが固定されていて解読計算量は定数時間になっているが、パラメータ選択時に現状及び今後の計算機能力の見積りを行い、安全性を保ちたい期間内には解読可能にならないような値を設定する。 このような計算量的安全性は、安全性の十分条件を与える情報理論的安全性よりは弱い安全性であるが、必要条件を与えるに過ぎない統計量的安全性よりは強い安全性であり、一般に広く利用されている暗号の多くはこの安全性に依拠している。.
新しい！!: P≠NP予想と計算量的安全性を持つ暗号 · 続きを見る »
計算機科学の未解決問題
計算機科学の未解決問題（けいさんきかがくのみかいけつもんだい）とは計算機科学における未解決の問題のこと。.
新しい！!: P≠NP予想と計算機科学の未解決問題 · 続きを見る »
自然な証明
計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。.
新しい！!: P≠NP予想と自然な証明 · 続きを見る »
自然数
自然数（しぜんすう、natural number）とは、個数、もしくは順番を表す一群の数のことである。集合論においては、自然数は物の個数を数える基数のうちで有限のものであると考えることもできるし、物の並べ方を示す順序数のうちで有限のものであると考えることもできる。 自然数を 1, 2, 3, … とする流儀と、0, 1, 2, 3, … とする流儀があり、前者は数論などでよく使われ、後者は集合論、論理学などでよく使われる（詳しくは自然数の歴史と零の地位の節を参照）。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。 数学の基礎付けにおいては、自然数の間の加法についての形式的な逆元を考えることによって整数を定義する。正の整数ないしは負でない整数を自然数と同一視し、自然数を整数の一部として取扱うことができる。自然数と同様に整数の全体も可算無限集合である。 なお、文脈によっては、その一群に属する個々の数（例えば 3 や 18）を指して自然数ということもある。.
新しい！!: P≠NP予想と自然数 · 続きを見る »
離散対数
代数学における離散対数（りさんたいすう、discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解(en:integer factorization)と以下の点が共通している：.
新しい！!: P≠NP予想と離散対数 · 続きを見る »
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).
新しい！!: P≠NP予想とNP完全問題 · 続きを見る »
P (計算複雑性理論)
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。.
新しい！!: P≠NP予想とP (計算複雑性理論) · 続きを見る »
RSA暗号
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現できる方式として最初に公開されたものである。.
新しい！!: P≠NP予想とRSA暗号 · 続きを見る »
ZFC
ZFC.
新しい！!: P≠NP予想とZFC · 続きを見る »
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
新しい！!: P≠NP予想と暗号理論 · 続きを見る »
暗号解読
暗号解読（あんごうかいどく、Cryptanalysis）とは、暗号を解読すること、あるいは解読法に関する研究を指す。 暗号の解読とは、暗号文を作成するのに用いた秘密情報（秘密の表記法や秘密の鍵など）にアクセスすることなく、暗号文を平文に戻すことである。これに対して、秘密情報を用いて暗号文を平文に戻すことは復号といい、解読と復号は区別することが多い。但し英語の"decryption"は両者の意味を持ち区別されない（以下、秘密情報のことを"鍵"と記す）。 他人に知られたくない情報を秘匿する手段として暗号が生まれるのと同時に、秘密を暴くための暗号解読も生まれたと考えられる。 研究としての暗号解読には、暗号 (Cipher) の解読だけではなく、デジタル署名の偽造、ハッシュ関数のコリジョン探索、あるいは暗号プロトコルの解読なども含まれる。.
新しい！!: P≠NP予想と暗号解読 · 続きを見る »
楕円曲線暗号
楕円曲線暗号（だえんきょくせんあんごう、Elliptic Curve Cryptography: ECC）とは、楕円曲線上の離散対数問題 (EC-DLP) の困難性を安全性の根拠とする暗号。1985年頃に ビクタ・ミラー (Victor Miller) とニール・コブリッツ (Neal Koblitz) が各々発明した。 具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。DSAを楕円曲線上で定義した楕円曲線DSA (ECDSA)、DH鍵共有を楕円化した楕円曲線ディフィー・ヘルマン鍵共有 (ECDH) などがある。公開鍵暗号が多い。 EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP.
新しい！!: P≠NP予想と楕円曲線暗号 · 続きを見る »
正当性 (計算機科学)
計算機科学における正当性（Correctness）とは、アルゴリズムがその仕様に照らして正しいことを意味する。「機能的」正当性とは、アルゴリズムの入出力動作に関する正当性である（すなわち、各入力に対して正しく出力を生成すること）。形式的検証を参照されたい。 完全正当性（Total Correctness）は、アルゴリズムが常に停止することも要求される。一方、部分正当性（Partial Correctness）は単に返ってくる答えが正しいことのみを要求する（常に答えが返ってくるとは限らない）。停止問題には汎用的解法はないので、完全正当性はより深い問題をはらんでいる。 例えば、整数を 1 から順に調べて奇数の完全数を探すとした場合、部分正当性を備えたプログラムを書くのは極めて簡単である（素因数分解を行って n が完全数かどうかを調べる）。しかし、そのプログラムが完全正当性を備えているとするには数論において未知の知識を必要とする。 正当性の証明は数学的証明でなければならず、アルゴリズムもその仕様記述も形式的に与えられなければならない（形式的仕様記述）。特にその証明は、そのアルゴリズムを特定のマシン上でプログラムとして実装したものについて正当性を意味するものではない。その場合メモリ量の限界を考慮する必要がある。 証明論におけるカリー・ハワード対応は、直観主義論理における機能的正当性の証明がラムダ計算における特定プログラムに対応するとしている。このような証明の変換を「プログラム抽出; program extraction」と呼ぶ。.
新しい！!: P≠NP予想と正当性 (計算機科学) · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: P≠NP予想と決定問題 · 続きを見る »
決定的アルゴリズム
決定的アルゴリズム（けっていてきアルゴリズム、deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。 決定的アルゴリズムは、同じ入力に対しては常に（ひとつの）同じ結果を返すという点で、関数の一種とみなせる。アルゴリズムはその結果の計算の具体的な手順を与えるものである。.
新しい！!: P≠NP予想と決定的アルゴリズム · 続きを見る »
擬似乱数
擬似乱数（ぎじらんすう、pseudorandom numbers）は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。 真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない（例：サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能）。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。 ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。 しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。.
新しい！!: P≠NP予想と擬似乱数 · 続きを見る »
懸賞金
懸賞金（けんしょうきん）、賞金（しょうきん）.
新しい！!: P≠NP予想と懸賞金 · 続きを見る »
懸賞金問題
懸賞金問題（けんしょうきんもんだい）とは、科学などの重要なテーマにおいて、解決者に対する懸賞金の支払いが、何らかの組織または個人から公式に発表された問題。.
新しい！!: P≠NP予想と懸賞金問題 · 続きを見る »
数学上の未解決問題
数学上の未解決問題（すうがくじょうのみかいけつもんだい）とは未だ解決されていない数学上の問題のことである。 未解決問題の定義を「未だ証明が得られていない命題」という立場を取るのであれば、そういった問題は数学界に果てしなく存在する。ここでは、リーマン予想のようにその証明結果が数学全域と関わりを持つような命題、P≠NP予想のようにその結論が現代科学・技術のあり方に甚大な影響を及ぼす可能性があるような命題、問いかけのシンプルさ故に数多くの数学者や数学愛好家達が証明を試みてきたような有名な命題を列挙する。.
新しい！!: P≠NP予想と数学上の未解決問題 · 続きを見る »
2000年
400年ぶりの世紀末閏年（20世紀および2千年紀最後の年）である100で割り切れるが、400でも割り切れる年であるため、閏年のままとなる（グレゴリオ暦の規定による）。。Y2Kと表記されることもある（“Year 2000 ”の略。“2000”を“2K ”で表す）。また、ミレニアムとも呼ばれる。 この項目では、国際的な視点に基づいた2000年について記載する。.
新しい！!: P≠NP予想と2000年 · 続きを見る »
ここにリダイレクトされます：
P-NP、P-NP問題、P=NP、P=NP予想、P=NP問題、PNP予想、PNP問題、P≠NP、P≠NP問題、P対NP問題。
