Meine Frage lautet wie folgt. Angenommen, ist ein NP-hartes Problem. Ist es bei einer beliebigen Instanz I von Π und der Annahme, dass ein Gegner weiß, dass diese Instanz leicht zu lösen ist, möglich, einen deterministischen Polynom-Zeit-Algorithmus zu finden, um diese bestimmte Instanz I zu lösen...
Ich habe mir kürzlich den folgenden Beweis ausgedacht, dass L = P P = NP impliziert. Angenommen, L = P. Sei A ein Problem in NP. Nach der Verifiziererdefinition von NP hat jede positive Lösung für A einen Zeugen, der in Polynomzeit verifiziert werden kann. Da P = L ist, kann dieselbe Lösung im...
Ich bin mir sicher, dass mit den folgenden Überlegungen etwas nicht stimmt, da sonst viele P- gegen NP-Untersuchungen eingeschränkt würden, aber ich kann meinen Fehler nicht feststellen: Für jede feste ganze Zahl definieren SieB k : = { ⟨ & phgr; ⟩ |k>0k>0k>0Bk:={⟨φ⟩|φis a wff of ZF and...
In Lance Fortnows Buch The Golden Ticket erwähnt er, dass Sie einen Polynom-Zeit-Algorithmus für ein NP-vollständiges Problem verwenden können, um einen schnelleren Algorithmus zu finden. Können Sie mir sagen, wie das gemacht wird? Und wenn dies erledigt ist, können Sie den neuen Algorithmus...
Concorde TSP ist ein Löser für TSP. SAT-Löser sind Löser für die boolesche Erfüllbarkeit. TSP und SAT sind NP-vollständig. Warum also die Zeit damit verbringen, Concorde TSP zu entwickeln, wenn es damals eine Fülle von SAT-Lösern auf dem Markt
Auf der Wikipedia-Seite zum P vs. NP-Problem gibt es einen Algorithmus, der SUBSET-SUM "löst", falls P = NP in Polynomzeit ist. (Es ist eine Idee, ein TM zu finden, das ein Zertifikat gibt). Aber es gibt "Ja" in Polynomzeit und läuft für immer, wenn die Antwort "Nein" ist. Es kann offensichtlich...