PNPとは?

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

PnP

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

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

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

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


PNP

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

PNP
PnP

P≠NP予想

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

(PNP から転送)

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であると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。

歴史

重要性

他の問題との関係

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となることが示されている。

現代暗号との関係

P≠NP予想は、暗号理論の分野でも重要な位置を占めている。

例えば、RSA暗号素因数分解ElGamal暗号および楕円曲線暗号(楕円曲線上のDLP)は離散対数問題の多項式時間による解法が存在しないことを安全性の根拠とした暗号であるが、これらの問題はどちらもクラスNPに属する問題に多項式時間帰着できる。仮にP≠NP予想が否定された場合(P=NPの場合)、素因数分解などが多項式時間で計算可能であることになり、これらの暗号の安全性は根底から覆ることになる。

それだけではなく、P=NPであれば「一方向性関数が存在しない」ことも証明できる。そして「一方向性関数が存在しない」ならば、多項式時間で破れない(暗号学的に安全な)公開鍵暗号ハッシュ関数擬似乱数が存在しないことが導かれる。逆に「一方向性関数が存在する」ならば、少なくとも多項式時間では破れない共通鍵暗号が構成できること、擬似乱数が存在することが証明されている。

また、暗号方式とその平文・暗号文ペアを与えられて鍵の1ビットを判定する問題は、(通常)多項式時間で検証可能であるから、この暗号方式が既知平文攻撃の条件で鍵探索が困難であることを証明できるならば、多項式時間で判定不可能であることを示したことになり、P≠NP予想を証明できたことになる。

このように、P≠NP予想は計算量的安全性を通じて現代暗号理論と密接に関係している。

参考文献

  • Stephen Cook, "The P versus NP Problem", 2000. [1] (PDF)
  • Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-94728-X. pp.372-377. (渡辺治・太田和夫 監訳, 『計算理論の基礎』, 共立出版社, 2000. ISBN 4-320-02948-8. pp.436-444)

関連項目





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

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「PNP」の関連用語

1
54% |||||

PNPのお隣キーワード

   

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

画像から探す

Gear 360

アークタッチBluetoothマウス

IdeaPad Y500

EPD

SDXC

鏡音リン・レン

Safari

LYNX 3D





PNPのページの著作権
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