私はコンピューター サイエンスの学生で、NP 問題の検証者ベースの定義を理解するのに問題があります。
定義は、「証明書」が与えられた場合、決定論的チューリングマシンによって多項式時間で検証できる場合、問題は NP にあると述べています。
しかし、証明書がまさに問題の解決策である場合はどうなるでしょうか? それはほんの少しであり、入力サイズによって明らかに多項式に制限されており、明らかに定数で検証可能であるため、多項式時間です。
したがって、各決定問題は NP に属します。
どこが間違っていますか？
しかし、証明書がまさに問題の解決策である場合はどうなるでしょうか? それはほんの少しであり、入力サイズによって明らかに多項式に制限されており、明らかに定数で検証可能であるため、多項式時間です。
なぜ「明らかに」？ソリューションの検証に指数関数的な時間を費やさなければならない場合がありますが、その場合、問題は NP である必要はありません。要点は、証明書が決定問題の単一ビットであっても、問題を解決するためにそのビットが 0 であるか 1 であるかがわからないということです。(あなたが常にそれを知っていれば、P または NP の決定問題は一定時間で解けるでしょう。)
解の長さが多項式であっても、すべての問題を多項式時間で検証できるわけではありません。巡回セールスマン問題を考えてみましょう。解が与えられた場合、与えられた解が都市のツアーであるかどうかのみを確認できますが、考えられるすべてのツアーを探索しない限り、それが最小の長さのツアーであるかどうかはわかりません。
したがって、ほとんどの場合、決定問題は NP 完全 (例: 一連の都市にツアーが含まれているかどうかを調べる) であり、最適化問題は NP 困難 (例: 最短距離のツアーを見つける) です。