NP困難
NP難問とは，YES/NO問題のことで，その問題の解を見つけることは，その問題の解が真であることをすぐに確認できる最も難しい問題の解を見つけるのと少なくとも同じくらい難しい問題である．NP難問の中には，有効な解がすぐに確認できる問題（NP問題）とそうでない問題がある．NP問題でもあるNP難問はNP完全問題と呼ばれるカテゴリーに入る．
少なくとも他の問題と同じくらいの難易度の問題で、すぐに解答を確認できる問題でも、すぐに確認できる問題の例（NPハードとNPハードの両方を兼ね備えている）。
ある旅行中のセールスマンは、自宅を出発点にして100の都市をドライブして回りたいと考えています。彼はガソリンの供給量が限られているので、合計1万キロしか走れません。彼は、ガソリンを使い切らずにすべての都市を訪れることができるかどうかを知りたいと思っています。
人々はこの問題を可能な限りの答えをテストするよりも速く解く方法を知りませんが、セールスマンがこれを行うことができる解が見つかった場合、それが真実であることをアルゴリズムでチェックすることができます。この問題は、トラベリングセールスマン問題としても知られています。
少なくとも他の問題と同じくらいの難易度で、すぐに解答を確認できるが、すぐには確認できない問題の例（NPハードだが、NPではない）。
誰かが単純にプログラムを起動したら
while(true){ continue; }とそれを止めることはありません、それは永遠に実行されますか？
この種の問題のすべての解決策を見つける方法は知られていませんし、これもチェックすることはできません。
質問と回答
Q:NP困難問題とは何ですか?
A: NP困難問題とは、コンピュータサイエンスで使われる数学的問題の一種で、イエス/ノー問題で、その解を見つけることが、解が真であることをすぐに確認できる最も難しい問題の解を見つけることと少なくとも同じくらい難しい問題のことです。
Q: すべてのNP困難問題に対して、動作する解を素早くチェックすることができますか?
A:いいえ、NP問題と呼ばれる一部のNP困難な問題だけが、素早くチェックできる解を持ちます。
Q: NP問題でもあるNP困難問題のカテゴリは何というのですか?
A:NP問題でもあるNP困難問題は、NP完全と呼ばれるカテゴリに分類されます。
Q: NP困難問題はすべてNP完全なのでしょうか?
A:いいえ、すべてのNP困難問題がNP完全ではありません。NP問題でもあるものだけがこのカテゴリーに入ります。
Q: NP困難問題は簡単に解けるのですか?
A:いいえ、NP困難問題は簡単ではありません。実際、解を見つけるのは、解が真であることがすぐに確認できる最も難しい問題の解を見つけるのと少なくとも同じくらい難しいのです。
Q: NP困難問題を解くことで得られるメリットはありますか?
A:はい、複雑な計算やモデリングが必要なこともあり、コンピュータサイエンス、物理学、社会科学など様々な分野で、NP困難問題を解くことによるメリットを得ることができます。
Q: NP困難問題を解く研究は進んでいるのでしょうか?
A:はい、NP困難問題は様々な分野での応用が期待されており、効率的なアルゴリズムや解法を見つけることが重要な意味を持つため、現在も研究が続けられています。
