私はコンピュータ科学の学生です。NPベリファイアのNP問題の定義を理解する上で問題があります。NPベリファイアベースの定義
定義には、「証明書」が与えられている確定的チューリングマシンによってポリノミー時間に検証できることがNPにあるということが示されます。
しかし、証明書が問題の解決策である場合はどうなりますか？これはほんの少しのことで、入力サイズによってポリノミナルに制限されています。そして、それは明らかに一定で、したがって多項式時間で検証可能です。
したがって、それぞれの決定問題はNPに属します。
どこが間違っていますか？
しかし、証明書が問題の解決策である場合はどうなりますか？これはほんの少しのことで、入力サイズによってポリノミナルに制限されています。そして、それは明らかに一定で、したがって多項式時間で検証可能です。
なぜ「明らかに」ですか？解決策を検証するために指数関数的な時間を費やさなければならない場合があります。この場合、問題はNP内にある必要はありません。要点は、証明書が意思決定問題のための単一のビットであっても、は、そのビットが問題を解決するために0または1であるべきかどうかを、は知らないことです。 （あなたがいつもそれを知っていれば、PまたはNPの決定問題は一定の時間内に解くことができます）
解が多項式であってもすべての問題を多項式時間で検証できるわけではありません。旅行セールスマンの問題を考えてみましょう。与えられた解が都市のツアーであるかどうかだけを検証することができますが、すべての可能なツアーを探索しない限り、最小のツアーであるかどうかは分かりません。最適化問題は、NP-ハード（例えば最小長ツアーを見つける）
ありながら決定問題はNP完全であるほとんどの場合そのため
は、（都市のセットは、ツアーが含まれているかどうかなどを見つけるために）つまり、問題がある場合、出力を証明書として使用すると、問題が検証された場合は1になり、問題が検証されない場合は0になります。したがって、検証マシンは証明書を出力として返すだけで済みます正しい答えを出す。 私の疑問は、npクラスの概念的理解ではなく、それを定義するために使用された形式主義の理解にあります。 – Simone
@Simone：あなたは証明書の定義が間違っていると思います。 [Wikipedia]（http://en.wikipedia.org/wiki/NP_%28complexity%29）は、検証する候補ソリューションとして*証明書*（暗黙的に）を定義しています。必ずしも1ビットである必要はありません。 –
必ずしもそうではありませんが、1つのシングルビットになることがあります。そのビットが問題の出力である場合、検証者の出力として使用できるよりも – Simone