Zustand T/F. Wenn jemand P = NP beweist, würde dies bedeuten, dass jedes Entscheidungsproblem in polynomieller Zeit gelöst werden kann. Ich denke, es ist falsch. Habe ich recht?Die Verbindung zwischen NP und Decision Pro
Wenn P = NP, bedeutet dies, dass jede Entscheidung Problem in NP in Polynomialzeit gelöst werden. Das heißt, jedes Entscheidungsproblem, bei dem "Ja" -Antworten effizient verifiziert werden könnten, könnte in polynomieller Zeit gelöst werden.
Dies ist nicht dasselbe wie zu sagen, dass alle Entscheidungsprobleme in polynomialer Zeit gelöst werden können. Zum Beispiel sind einige Entscheidungsprobleme (wie das Halteproblem) unentscheidbar, was bedeutet, dass sie überhaupt nicht entschieden werden können. Proving P = NP ändert das nicht.
Sie haben Recht. Aber Sie sollten näher erläutern, warum Sie es für falsch halten, um zu sehen, ob Sie aus den richtigen Gründen Recht haben. – Solarflare
Ich denke, das P ist die Menge der Entscheidungsproblem, die in polynomieller Zeit gelöst werden kann. Aber es bedeutet nicht, dass jedes Entscheidungsproblem in polynomieller Zeit gelöst werden kann. – sower