いままでちゃんと使えてなかったのでメモ。
ムツカシそうな問題に対して、それっぽい発言したいときには「こいつぁNP困難っぽいや」って言っておけば大丈夫なはず。
- WikipediaのNP困難の記述によると「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」
- 停止問題やNPではないムツカシそうな問題（巡回セールスマン問題などのyes/noの判定問題ではないもの）に対しても「NP困難」は使えるらしい
誤用になりやすそうな用例など
- 「こいつぁNPっぽいや」
- WikipediaのPの記述では「PがNPに含まれることは自明である」らしいので、何も主張していないのに近くなってしまう
- 「こいつぁNP完全っぽいや」
- 巡回セールスマン問題などのyes/noで答えられる判定問題ではないものが話題のときに使ってしまうとコイツ分かってねぇ系の烙印押されてしまうこわい
その他の活用シーン
「あれ？これってむずかしそう...」って思ったとき、「NP困難」をつけてググると何がどうむずかしいのかのヒント探せそう