>>89

>＃>88の「NP困難問題」と言ってしまうとちょっと行き過ぎですね。NP困難はどんな難しい問題も含むので、
>＃停止問題とかもNP困難になります。

は?
だったらあらゆるNP問題を停止問題に多項式時間帰着出来る事を証明してみろよ?

>この場合「NP完全」というのが多分正解

お前まさか、停止問題がNP困難ではないがNP完全ではあると言っているの?
NP完全はNP困難問題のうち、決定問題の物であり、関数問題であるNP困難の部分集合だろ?

悪い事は言わない。
赤っ恥さらす前に勉強してきた方が良いぞ!!