np完全問題とは何ですか

例とか、特にどんなところが難しいかを教えてください。
友達の話ではチンプンカンプンで、何の為にそれを使って議論してるか分かりません。

No.3 回答者： bender 回答日時： 2005/11/08 19:44

Wikipedia 英語版の “NP-complete” （やその他）に以下のように書いてあります。

A decision problem C is NP-complete if
1. it is in NP and
2. it is NP-hard, i.e. every other problem in NP is reducible to it.

ここで “decision problem” というのは、答えが Yes/No のいずれかで答えられるような種類の問題のことです。
また、始めの条件１に書いてあるNP と呼ばれる問題の集まりは、問題の答え（Yes/No）とその「求め方」がわかってしまえば、その答えが正しいかどうかのチェックは「素早く」できてしまう問題、そういった問題の集まり、とおおよそいえると思います。
さらに、条件２にある NP-hard と呼ばれる問題の集まりは、（すでに述べた）NPと呼ばれる問題のどの問題よりも、同じかそれ以上に難しいといえる問題の集まりことです。

この２つの条件を満たす NP-complete と呼ばれる問題になぜ関心が寄せられるのかというと、この条件からもわかるように、NP-complete 問題のうちどれか一つについて「素早く」解く方法が見つかると、すべてのNP 問題が「素早く」解けてしまうことになるからです。「興味深い問題」の多くは NP に含まれているので、それらすべてが「素早く」解けてしまう方法がみつかったらえらいことでしょうね。

ただ、NP-complete の問題はおそらく「素早く」は解けないのだろう、といわれているのですが、まだその証明がされていません。質問された方がその証明を発見した際には、あるいは、素早い解法を見つけた際には、その論文の謝辞に僕の名前も加えてもらえますか？

No.2 回答者： uyama33 回答日時： 2005/11/07 20:31

　暗号を盗聴者が解読するのに

とってもたいへんなら盗聴しても
無意味になります。
　もちろん正式な資格のある
ものは簡単に復号化出来る必要があるのですが、
盗聴者があきらめるほど計算がたいへんなら
暗号に利用できそうですね。
　計算のたいへんさを計れたら
暗号に応用できるか否か判断できますね。
．．
　もっとも、
ナップサック暗号は
上の話がそんなに簡単ではないと言うことの
具体例のようです。
．．
参考文献は
数論アルゴリズムと楕円暗号理論入門
著者は　Ｎ．コブリッツ

No.1 回答者： BLUEPIXY 回答日時： 2005/11/06 02:59

http://ja.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8
にＮＰ完全問題の例が載っています
問題の答えを求めるには総当たり（とか）で答えを求めれば求まるということがわかっていても、問題の大きさが大きくなるにつれて爆発的に計算量が増えるような問題は一般的に最適解を求めることが困難です。
概ねそういうことかと思います