<a href="http://bsg.to/mt/archives/200608/2006-08-26T11:17.shtml">一般人無双R: PとかNPとかで悩んでます</a>

横から勝手に.
そういうときはWikipediaよりもComplexity Zooの方が信頼が置けます. Scott Aaronson先生作.

NP完全とNP困難の違いというのは、その問題自身がNPに入ってるかどうかということですが、NPな問題から多項式時間で帰着できるのにそれ自身がNPじゃないというのは納得いかない！
クラスNPの中身は当然NTMで多項式時間で解けるので、多項式時間＋多項式時間＝多項式時間ということでNP困難＝NP完全⊆NPでは？

EXP完全な問題は, (多分)NPに入らないが, NP困難なので, 判定版に限ってもそれは嘘.

いやしかし……電子情報通信学会論文誌４月号にのってた「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」でぷよの連鎖数の計算がNP完全って載ってたような気がするし……。学者様でもNP完全とNP困難の区別が付かないの？？

多分, 連鎖数判定問題がNP完全で, 連鎖数計算問題がNP困難って書いてあると思いますけども. この辺に関しては, 著者本人に聞くのが一番早いと思いました→ぷよまつの形式聴牌な日常 2006/04/15 続・ぷよ論文

ともあれ、決定問題じゃないような多項式時間問題はどういうクラスに入るんでしょう……？
決定問題じゃなくて多項式時間で解けるようなものっていくらでもありますよね？？（例えば以下）
(中略)
Pな問題から多項式時間で帰着するからこれはP困難クラス？ｗ

NPとPは判定問題の集合. FPというクラスがあって, これはPの探索版 (教科書等で見たことないな). FNPというクラスもあって, こっちはNPの探索版.

イメージとしてはこんなんですよ.

一応はNP=Pの可能性もあるので, 正確な図ではありません. NP-completeな問題はPの外にあるし.