Erklären Sie den Nachweis von Vinay Deolalikar dass P! = NP [geschlossen]

Question

Vor kurzem gab es eine Papier schwimmend von Vinay Deolalikar bei HP Labs um die, dass P! = NP .

Könnte jemand erklären, wie dieser Beweis Werke für uns weniger mathematisch Menschen geneigt?

Answer 1

Ich habe nur durch das Papier gescannt, aber hier ist eine grobe Zusammenfassung, wie es alle hängen zusammen.

Von Seite 86 des Papiers.

  

... Polynomzeit   Algorithmen gelingt durch sukzessives   „Aufbrechen“ das Problem in   kleinere Teilprobleme, die verbunden sind,   miteinander durch bedingte   Unabhängigkeit. Folglich Polynom   Algorithmen können nicht lösen   Probleme in Regimen in dem Block, deren   Ordnung ist das gleiche wie die darunter liegenden   Problemfall erfordern gleichzeitige   Auflösung.

Andere Teile des Papiers zeigen, dass bestimmte NP-Probleme können nicht auf diese Weise aufgebrochen werden. So NP / = P

Ein großer Teil des Papiers ausgegeben definieren bedingte Unabhängigkeit und beweisen diese beiden Punkte.

Answer 2

Dick Lipton hat einen schönen Blogeintrag über das Papier und seine ersten Eindrücke davon. Leider ist es auch technisch. Von dem, was ich verstehen kann, scheint Deolalikar Haupt Innovation, einige Konzepte zu sein aus dem statistischen Physik zu verwenden und endlicher Modelltheorie und sie auf das Problem zu binden.

Ich bin mit Rex M mit diesem, einig Ergebnissen, vor allem mathematisch diejenigen, können nicht auf Menschen, die die technische Meisterschaft fehlen ausgedrückt werden.

Answer 3

Ich mochte diesen ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ):

  

Sein Argument dreht sich um eine bestimmte Aufgabe, die Boolesche Erfüllbarkeit Problem, das eine Sammlung von logischen Aussagen fragt, ob alle gleichzeitig wahr sein kann, oder ob sie sich gegenseitig widersprechen. Dies ist bekannt, ein NP-Problem sein.

     

behauptet Deolalikar gezeigt haben, dass   es gibt kein Programm, das abgeschlossen werden kann   es schnell von Grund auf, und dass es   daher ist kein P Problem. Seine   Argument beinhaltet die raffinierte Verwendung von   statistische Physik, wie er verwendet   mathematische Struktur, die folgt,   viele der gleichen Regeln wie eine zufällige   physikalisches System.

Die Auswirkungen der oben können ganz erheblich sein:

  

Wenn das Ergebnis steht, würde es beweisen   dass die beiden Klassen P und NP sind nicht   identisch und strenge Grenzen auferlegt werden   was Computer erreichen kann -   was bedeutet, dass viele Aufgaben sein können   im Grunde nicht reduzierbar komplex.

     

Für einige Probleme - einschließlich   Faktorisierung - das Ergebnis nicht   klar sagen, ob sie gelöst werden   schnell. Aber eine große Unterklasse   Probleme „NP-complete“ genannt wären   verurteilt. Ein berühmtes Beispiel ist die   Reiseproblem - zu finden,   der kürzeste Weg zwischen einem Satz von   Städte. Solche Probleme können überprüft werden   schnell, aber wenn P ? NP dann gibt es   kein Computerprogramm, das abgeschlossen werden kann   sie schnell von Grund auf neu.

Answer 4

Das ist mein Verständnis der Beweistechnik: er Logik ersten Ordnung verwendet alle Polynomzeit Algorithmen zu charakterisieren und dann zeigt, dass für große SAT Probleme mit bestimmten Eigenschaften, dass kein Polynomialzeitalgorithmus ihre Erfüllbarkeit bestimmen kann.

Answer 5

Eine andere Denkweise darüber, was völlig falsch sein kann, aber es ist mein erster Eindruck, als ich es beim ersten Durchgang gerade las, ist, dass wir denken, die Zuordnung / Clearing Bedingungen in der Schaltung Zufriedenheit als Form- und Bruch Cluster von ‚geordnete Struktur‘, und dass er dann statistische Physik verwendet um zu zeigen, dass es nicht genügend Geschwindigkeit in den Polynom-Operationen ist es, diese Operationen in einem bestimmten „Phasenraum“ von Operationen, da diese „Cluster“ am Ende als zu weit führen auseinander.

Answer 6

Dieser Nachweis müßte alle Klassen von Algorithmen decken, wie kontinuierliche globale Optimierung .

Zum Beispiel in der 3-SAT Problem haben wir Variablen zu bewerten, alle Alternativen von Tripel dieser Variablen bzw. deren Negationen zu erfüllen. Schauen Sie, dass x OR y kann in der Optimierung

geändert werden

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

und analog sieben Begriffe für alternative von drei Variablen.

Das Finden der globale Minimum einer Summe solcher Polynome für alle Bedingungen würde unser Problem lösen. ( Quelle )

Es wird aus Standard kombinatorischen Techniken auf die kontinuierlichen Welt using_gradient Methoden, lokale Halben Entfernen Methoden, evolutionäre Algorithmen. Es ist völlig anders Reich - numerische Analyse - (?) Ich habe nicht ein solcher Nachweis könnte wirklich Abdeckung

glauben

Answer 7

Es ist erwähnenswert, dass mit Beweisen der Feststellung, „der Teufel steckt im Detail“. Die Übersicht auf hoher Ebene ist offensichtlich so etwas wie:

  

Einige irgendeine Art von Beziehung   zwischen den Elementen zeigen, dass diese   Beziehung impliziert X und dass   Y bedeutet und damit mein Argument ist   gezeigt.

Ich meine, es kann sein über Induction oder jede andere Form Dinge zu beweisen, aber was ich sage, ist die hohe Übersicht nutzlos ist. Es gibt keinen Punkt es zu erklären. Obwohl sich die Frage, in die Informatik betrifft, ist es am besten Mathematiker links (dachte, es sicherlich unglaublich interessant ist).