Was wäre ein P = NP Beweis wie sein hypothetisch?

StackOverflow https://stackoverflow.com/questions/900273

Frage

Wäre es ein Polynomialzeitalgorithmus zu einem bestimmten NP-vollständigen Problem, oder einfach nur abstrakte Argumentationen sein, die Lösungen für NP-vollständige Probleme zeigen, existieren?

Es scheint, dass die eine spezifische algoithm viel hilfreicher ist. Damit alle uns polynomial tun müssen, um ein NP-Problem zu lösen, ist es in das spezifische NP-vollständige Problem zu konvertieren, für die der Nachweis eine Lösung hat, und wir sind fertig.

War es hilfreich?

Lösung

P = NP: „Die 3SAT Problem ist ein klassisches NP vollständiges Problem in diesem Beweis. zeigen wir einen Algorithmus, um es zu lösen, dass eine asymptotische hat gebunden von (n ^ 99 log log n). Zuerst haben wir ... "

!

P = NP. „Angenommen, es ein Polynom-Algorithmus für die 3SAT Problem Diese würde bedeuten, dass .... die durch ..... impliziert wir .... und dann tun können ... und dann ... was unmöglich ist. für 3SAT Das war alles auf einem Polynomialzeitalgorithmus sagt. So P ! = NP. "

UPDATE : Vielleicht so etwas wie dieses Papier (für P! = NP).

UPDATE 2 : Hier ist ein Video von Michael Sipser skizzieren einen Beweis für P! = NP

Andere Tipps

Rufen Sie mich pessimistisch, aber es wird so aussehen:

...

∴, P ≠ NP

QED

Es gibt einige Meta-Ergebnisse über das, was ein P = NP oder P ≠ NP Beweis kann nicht aussehen. Die Details sind sehr technisch, aber es ist bekannt, dass der Nachweis nicht erbracht werden kann

  • Relativierung , welche Art von bedeutet, dass der Nachweis Verwendung der genauen Definition von Turing-Maschine verwendet, da mit einigen Modifikationen ( „Orakeln“, wie sehr leistungsfähige CISC-Befehle hinzugefügt, um den Befehlssatz) P = NP, und mit einigen anderen Änderungen, P ≠ NP machen muß. Siehe auch diesem Blog-Eintrag für eine schöne Erklärung von Relativierung.

  • natürlich , eine Eigenschaft von mehreren klassischen Schaltungskomplexität Beweise,

  • oder algebrizing , eine Verallgemeinerung von Relativierung.

Es könnte die Form demonstriert nehmen, dass P ≠ NP unter der Annahme zu einem Widerspruch führt.

Es ist vielleicht nicht zu P und NP auf einfache Art und Weise ... jetzt viele Sätze basieren auf P angeschlossen werden! = NP, so erweist sich als eine Tatsache unwahr zu sein, angenommen würde einen großen Unterschied machen. Auch erweist sich so etwas wie konstantes Verhältnis Näherung für TS sollte genug IIRC sein. Ich denke, das Vorhandensein von NPI (GI) und anderen Gruppen auch auf P basiert! = NP, so macht jeder von ihnen gleich P oder NP könnte vollständig die Situation verändern.

IMHO alles geschieht jetzt auf einer sehr abstrakten Ebene. Wenn jemand etwas über P beweist = /! = NP, ist es nicht eine dieser Sätze oder sogar ein spezielles Problem zu erwähnen.

Wahrscheinlich wäre es in Form einer Reduktion von einem NP-Problem zu einem P Problem sein. Sehen Sie sich die Wikipedia-Seite über Reduzierungen .

oder

Wie dieser Beweis Vorschlag Vinay Deolalikar .

Set N gleich die multiplikative Identität. Dann NP = P. QED. ; -)

Der einfachste Weg ist, um zu beweisen, dass es eine Polynomzeit Lösung in der Klasse für die Probleme ist NP-vollständig. Dies sind Probleme, die in NP sind und reduzierbar zu einem der bekannten np Problem. Das bedeutet, dass Sie einen schnelleren Algorithmus geben könnten die ursprüngliches Problem, das durch Stephen zu beweisen cook- oder viele andere, die auch NP-Complete gezeigt wurden, sein. Siehe Richard Karp Samen Papier und dieses Buch interessanter Probleme. Es hat sich gezeigt, dass, wenn Sie eines dieser Probleme zu lösen, die gesamte Komplexität Klasse zusammenbricht. edit: Ich muss hinzufügen, dass ich zu meinem Freund sprach, die Quantenberechnung studiert. Obwohl ich hatte keine Ahnung, was es bedeutet, sagte er, dass ein sicherer Beweis / Experiment? in der Quantenwelt die gesamte Komplexitätsklasse machen könnte, ich meine das Ganze, strittig. Wenn jemand hier mehr darüber weiß, bitte antworten.

Es gibt auch zahlreiche Versuche unternommen, um das Problem gewesen, ohne einen formalen Algorithmus zu geben. Sie könnten versuchen, den Satz zu zählen. Theres den Robert / Seymore Beweis. Die Menschen haben auch versucht, es zu lösen, um den bewährten diagonlization Beweis verwenden (auch zu zeigen, verwendet, dass es Probleme, die Sie nie lösen können). Razborov zeigte auch, dass, wenn es bestimmte Einwegfunktionen dann einen Beweis nicht eine Auflösung geben kann. Das bedeutet, dass neue Techniken, um diese Frage zu lösen, erforderlich.

Die 38 Jahre seit der ursprünglichen Papier veröffentlicht worden ist, und es gibt immer noch keine Anzeichen für einen Beweis. Nicht nur, dass aber viele Probleme, die Mathematiker vor dem Begriff der Komplexität aufwirft Klassen hatte kam wurde NP erwiesen. Deshalb viele Mathematiker und Informatiker Wissenschaftler glauben, dass einige der Probleme, so sind von grundlegender Bedeutung, dass eine neue Art von Mathematik benötigt werden, um das Problem zu lösen. Sie müssen bedenken, dass die besten Köpfe Menschheit ohne Erfolg dieses Problem in Angriff genommen haben, zu bieten hat. Ich denke, es sollte das Puzzle mindestens Jahrzehnte bevor jemand Risse sein. Aber selbst wenn es eine Polynom Zeitlösung ist die Konstanten oder der Exponent könnten so groß sein, dass es in unseren Problemen nutzlos wäre.

Es gibt eine ausgezeichnete Umfrage zur Verfügung, die meisten Ihrer Fragen zu beantworten: http: // www .scottaaronson.com / papers / pnp.pdf .

Sicherlich ein beschreibender Beweis ist das nützlichste, aber es gibt andere Kategorien von Beweis: Es ist möglich, zum Beispiel ‚Existenzbeweise‘ zu schaffen, die zeigen, dass es möglich ist, eine Antwort finden ohne zu finden (oder manchmal sogar darauf hindeutet, wie zu finden) die Antwort.

Es wäre fast wahrscheinlich aussehen genau wie eine von diese

Gute Frage; es könnte so oder Form. Offensichtlich wäre der spezifische Algorithmus hilfreicher, ja, aber es gibt keine Bestimmung, dass das wäre der richtige Weg sein, daß ein theoretischer P = NP Beweis auftreten würde. Da die Art der NP-vollständige Probleme und wie häufig sie sind, so scheint es, dass mehr Mühe in die Lösung dieser Probleme gestellt worden, als es in die Lösung der theoretischen Argumentation Seite der Gleichung gesetzt worden, aber das ist nur Vermutung.

Jeder relativ schlechter Beweis dafür, dass P = NP ist wirklich nicht. Es würde bedeuten, dass der folgende explizite 3-SAT-Algorithmus in polynomialer Zeit läuft:

  

Alle Programme aufzuzählen. Auf rund i , laufen alle Programme nummeriert   weniger als i für einen Schritt. Wenn   ein Programm endet mit einem    erfüllt Eingabe in die Formel , kehren true . Wenn ein Programm   endet mit einem formalen Beweis, dass   keine solche Eingabe existiert , Rückkehr    false .

Wenn P = NP, dann gibt es ein Programm gibt, die in O läuft (Poly (N)) und gibt ein befriedigendes Eingabe in die Formel, wenn eine solche Formel besteht.

Wenn P = coNP existiert ein Programm, das in O läuft (Poly (N)) und gibt einen formalen Beweis, dass keine Formel vorhanden ist, wenn keine Formel vorhanden ist.

Wenn P = NP, dann da P unter Komplement NP = coNP geschlossen ist. So gibt es ein Programm, das in O läuft (Poly (N)) und tut beides. Das Programm ist das k 'th Programm in der Aufzählung. k O (1) ! Da es in O läuft (Poly (N)) unsere Brute-Force-Simulation erfordert nur

  

k * O (Poly (N)) + O (Poly (N)) ^ 2

rundet, sobald sie das Programm in Frage erreicht. Als solche führt die Brute-Force-Simulation in Polynomzeit!

(Beachten Sie, dass k exponentiell in der Größe des Programms, dieser Ansatz nicht wirklich machbar ist, aber es legt nahe, dass es schwierig sein würde, einen relativ schlechten Beweis dafür, dass P = NP zu tun, auch wenn es der Fall wäre).

Zu einem gewissen Grad, wie die Form eines Beweis hängt von Ihrer philosophischen Sicht haben muss (= die Axiome Sie erachten um wahr zu sein) - zum Beispiel als ein

Der Beweis aus wäre einen Widerspruch zu der Annahme, ableiten, dass mindestens ein Element (Problem) der NP nicht auch ein Element von P.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top