p-n-pとは?

Weblio 辞書 > コンピュータ > IT用語辞典 > p-n-pの意味・解説 

PnP

フルスペル:Plug and Play
読み方ピーエヌピー
別名:プラグアンドプレイ

PnPとは、パソコン周辺機器拡張ボードなどを接続した際に、自動的機器検出適切な設定を行うシステムのことである。Windows 95初め本格的実装された。

従来パソコン周辺機器接続して利用したい場合には、ただ物理的接続するだけではなくデバイスドライバ割り込み処理I/Oアドレスリソース割り当てといった設定ユーザーが行う必要があった。そのため周辺機器使用するには高度で複雑な知識を必要とした。PnPの実現により、複雑な知識を持たない一般的なユーザでも気軽に周辺機器利用できるようになった

なお、機器接続するだけでネットワーク接続可能にするプロトコルは、UPnPユニバーサルプラグアンドプレイ)と呼ばれている。似たような言葉として、電源を入れたまま機器抜き差しが可能であるという意味のホットプラグ活線挿抜)などもある。


PNP

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2010/08/23 16:43 UTC 版)

PNP
PnP

P≠NP予想

(p-n-p から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/08/25 07:00 UTC 版)

P≠NP予想(P≠NPよそう、: P is not NP)は、計算複雑性理論(計算量理論)におけるクラスPクラスNPが等しくないという予想である。P対NP問題(PたいNPもんだい、: P versus NP)と呼ばれることもある。

理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年クレイ数学研究所ミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。

概要

クラスPとは、決定性チューリング機械において、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠(Witnessという)が与えられたとき、多項式時間でWitnessの正当性の判定(これを検証という)が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。

仮にP=NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。NP問題は数千種類が知られているが、P=NPが示された途端にそれらが全て多項式時間で解けるとは俄かに信じ難いことである。更に、P≠NPであろうと見越してNP完全問題の入力nビットについての計算量をO(kn)と置き、せめて基底のkを改善しよう(例えばk=2を1.9や1.8等に)という試みでさえ、ある程度進展した後に行き詰ることが知られている。これらの観察がP≠NP予想の重要な根拠の一つとなっている。


一方、P=NPと予想する研究者も皆無ではない。ドナルド・クヌースはその一人であり、次のような論拠を挙げている[1]

  • P≠NPを証明する試みはことごとく失敗している(後述の#歴史参照)
  • NP問題をnMステップで解くアルゴリズムがあるとする。このMは例えば10↑↑↑↑3のような有限ながらも巨大な値を取れる。するとnビットの入力についてnM個の論理演算や加算演算、シフト演算などを実施する途轍もない種類のアルゴリズムが考えられる訳で、これが全て失敗するとは信じ難い

但し彼は同時に次のようにも述べている。

「だが私が最も言いたいのは、例えP=NPが証明できたとしても、それが実用上役に立つとは思えないということだ。何故ならそうした証明はまず間違いなく非構成的だろうからだ。Mは存在すると思うが、人類がその値を知ることは決してないだろうとも思う。それどころかMの上界を求めることすら出来ないのではないか」[1]

彼は存在が証明されているが実装は現実的に不可能と考えられているアルゴリズムの例を複数列挙している。

歴史

起源

P vs.NP問題が定式化されたのは1971年だが、関連する問題やその難しさ、潜在的な影響などについて先駆的な考察があった。

ナッシュの手紙(1955年)

ジョン・ナッシュは、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた[2]。もしこれを証明できれば(ナッシュは証明不能と考えていたが)、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。

ゲーデルの手紙(1956年)

1956年、クルト・ゲーデルは癌で入院していたジョン・フォン・ノイマン宛に手紙を書いた。その中で彼は定理の証明(今日ではcoNP完全であると判っている)を2次または線形時間で解けるだろうかと意見を求め[3]、もしそれが可能なら数学の新定理の発見を自動化できるだろうと指摘した。
これに対するノイマンの返事は伝わっておらず、ノイマンは翌1957年に死去した。ハルトマニスは、この手紙がノイマンが健康だった間に出されていれば、この問題は既に解けるか研究史がもっと短縮されていたのではないかと嘆いている[3]

証明の試みと難しさ

P≠NP予想の面白さと難しさは、複雑性クラスを分離するために利用・考案されてきた様々な証明手法が、証明手法自体の本質的な限界によりP≠NPを証明できないという、不可能性の証明がこれまで幾度も得られてきた点にある。つまり、時代が進めば進むほど証明の可能性が原理的に狭められてきた。だからと言ってP=NPの方が確からしいと傾いた訳でもなく、新たな証明手法が必要だと考えられてきた点がまた特徴的である。以下にあらましを述べる。本節は主に岡本 (2009)の解説記事に基づく。

相対化

複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法がある。これは濃度の違いに着目して複雑性クラスを分離するもので、P≠EXPTIME(Hartmanis & Stearns (1965))を示す際などに適用された。 このような集合論的な証明手法の特徴として「相対化」と呼ばれる性質の保存がある。複雑性クラスCをオラクルAで相対化するとは、クラスCに属する計算機にオラクルAを付与した新しい複雑性クラスCAを作ることである。ここで、複雑性クラスC,Dについて集合論的な手法によってC≠Dが示されたとすると、CA≠DAが同時に成り立つ。同様に、集合論的な手法によってC=Dが示された場合はCA=DAがどのようなAについても成り立つ。

ところが、Baker, Gill & Solovay (1975)は次のことを示した。

  • PA≠NPAとなるオラクルAと、PB=NPBとなるオラクルBが存在する

この結果により、集合論的な証明手法ではP≠NPを原理的に証明できないことが判明した。

自然な証明

1980年代に入り、集合論的手法ではない回路計算量に着目する新しい証明手法が開発された。これは今日「自然な証明」と呼ばれるもので、AC0≠NC1Furst, Saxe & Sipser (1984))やmP/poly≠NP(Razborov (1985))などの成果を挙げた。この手法からP≠NPを見る場合は、Pを包含するクラスP/poly英語版に着目してP/poly≠NPを証明することが問題となる(そこから直ちにP≠NPが従う)。

ところが、当初の期待にも関わらず、P/poly≠NPに向けた進展はぱったり止まってしまい、やがて研究者の間で何か原因があるのではないかと議論されるようになった。そんな中、Razborov & Rudich (1997)はその原因を突き止め、次のことを示した。

  • 素因数分解の困難性を仮定すると、自然な証明ではP/poly≠NPを証明できない

「自然な証明」は名前の通り自然な発想に基づく証明戦略であり、それまで得られた複雑性クラスの分離に関する殆ど全ての証明で利用されていた。ところが、そうした証明手法ではP≠NPを原理的に証明できないことが判明したのである。RazborovとRudichはこの成果により2007年のゲーデル賞を受賞した。但し彼らが定義した「自然な証明」には幾つか技術的な条件があることから、この条件を巧妙に回避することで障害を乗り越えようとする研究方向も存在する。

代数化

集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP=PSPACE(Lund,Fortnow,Karloff,Nisan,Shamir(1989))やMAEXE P/poly(Buhrman, Fortnow & Thierauf (1998))、PP Size(nk)(Vinodchandran (2005))などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。

ところが、こうした証明方法ではP≠NPを証明不可能であることがAaronson & Widgerson (2009)により示された。彼らは「代数化」という概念を導入し、算術化された集合論的方法によって得られた従来の結果は全て代数化できることを示した。一方、P=NPとP≠NPは何れも代数化できないことを示した。このため、算術化された集合論的手法による結果は全て代数化できるとすると、この方法ではP=NPとP≠NPは原理的に証明できないことになる。

その他の方法

以上の経緯から現在では、P≠NPを証明するためには、相対化されず、自然な証明ではなく、代数化できない証明手法が必要だと考えられている。そのような証明手法の候補は幾つかあるが、それらもまた何らかの限界が潜在しているかも知れず、証明手法に関する本質的な理解が今後に求められている。

その他の方向性として、P≠NPがそもそもZFCから独立なのではないかと疑う向きがあるが、こちらについても現状では否定的な結果が得られている。

重要性

他の問題との関係

NP完全
1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P=NPとなる。
NP完全には含まれない問題
NP-(P∪NP完全)となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補としてグラフ同型問題がある。
coNP
NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。

脚注

[ヘルプ]
  1. ^ a b Knuth, Donald E. (2014年5月20日). “Twenty Questions for Donald Knuth”. informit.com. InformIT. 2017年6月10日閲覧。
  2. ^ NSA (2012年). “Letters from John Nash (PDF)”. 2017年6月10日閲覧。
  3. ^ a b Hartmanis, Juris. “Godel, von Neumann, and the P = NP problem” (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101-107. http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf.  この論文にはゲーデルの手紙の英訳(抄)も記載されている

参考文献

関連項目





英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

「p-n-p」に関係したコラム

  • FXやCFDのRMIとは

    FXやCFDのRMI(Relative Momentum Index)とは、テクニカル指標のモメンタムを用いて、値動き幅から相場の売られ過ぎ、あるいは、買われ過ぎを判断するためのテクニカル指標のことで...

  • ETFの銘柄一覧

    ETFの銘柄数は2012年9月の時点で約140あります。そして、いずれの銘柄にも価格の連動となる対象の商品があります。ここでは、ETFの銘柄をジャンルごとに紹介します。表の「コード」は株式コード、「市...

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「p-n-p」の関連用語











p-n-pのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

Windows 95

ルーター

Mac OS X Server

レグザタブレットAT830

リバースケーブル

arrows NX F-01J

マイクロフォーサーズシステム

新型MacBook Air





p-n-pのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2017 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリPnPの記事を利用しております。
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのPNP (改訂履歴)、P≠NP予想 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2017 Weblio RSS