横から勝手に. そういうときはWikipediaよりもComplexity Zooの方が信頼が置けます. Scott Aaronson先生作. NP完全とNP困難の違いというのは、その問題自身がNPに入ってるかどうかということですが、NPな問題から多項式時間で帰着できるのにそれ自身がNPじゃ…