Ist Norbert Blums Beweis für 2017, dass korrekt ist?

232

Norbert Blum veröffentlichte kürzlich einen 38-seitigen Beweis, dass . Ist es richtig?PNP

Auch zum Thema: Wo sonst (im Internet) wird über deren Richtigkeit diskutiert?

Hinweis: Der Fokus dieses Fragetextes hat sich im Laufe der Zeit geändert. Siehe Fragenkommentare für Details.

Warren Schudy
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Bjørn Kjos-Hanssen

Antworten:

98

Wie bereits erwähnt, widerlegt das Beispiel von Tardos den Beweis eindeutig. es gibt eine monotone Funktion, die mit CLIQUE auf T0 und T1 übereinstimmt, aber in P liegt. Dies wäre nicht möglich, wenn der Beweis korrekt wäre, da der Beweis auch für diesen Fall gilt. Können wir den Fehler jedoch lokalisieren? Aus einem Beitrag im Blog von Lipton geht hervor, an welcher Stelle der Beweis fehlschlägt:

Der einzelne Fehler ist ein subtiler Punkt im Beweis von Satz 6, nämlich in Schritt 1, auf Seite 31 (und auch 33, wo der doppelte Fall erörtert wird) - eine anscheinend offensichtliche Behauptung, dass alle entsprechenden Klauseln enthält, die in enthalten sind etc, scheint falsch. C N F ' ( g )CgCNF(g)

Um dies näher zu erläutern, müssen wir auf die Beweis- und Approximationsmethode von Berg und Ulfberg eingehen, die den ursprünglichen Beweis von Razborov für die exponentielle monotone Komplexität für CLIQUE in Form von DNF / CNF-Schaltern wiedergibt. So sehe ich es:

Zu jedem Knoten / Gate eine Logikschaltung (enthaltende binäre OR / AND - Gatter nur), eine konjunktiven Normalform , eine disjunktive Normalform und Approximatoren und sind angebracht. und sind einfach die entsprechenden disjunktiven und konjunktiven Normalformen des Gate-Ausgangs. und sind ebenfalls disjunktive und konjunktive Formen, jedoch von einigen anderen Funktionen, die die Gate-Ausgabe "approximieren". Sie müssen jedoch eine begrenzte Anzahl von Variablen in jedem Monom fürβ C N F ( g ) D N F ( g ) C k g D R g C N F D N F D R g C k g D R g C k ggβCNF(g)DNF(g)CgkDgrCNFDNFDgrCgkDgr(kleiner als eine Konstante r) und in jeder Klausel für (kleiner als eine Konstante k).Cgk

Mit dieser Annäherung wird der Begriff "Fehler" eingeführt. Wie wird dieser Fehler berechnet? Wir interessieren uns nur für eine Menge T0 von Eingängen, für die unsere Gesamtfunktion den Wert 0 annimmt, und T1 von Eingängen, für die unsere Gesamtfunktion den Wert 1 annimmt (ein "Versprechen"). Nun betrachten wir bei jedem Gate nur die Eingänge von T0 und T1, die korrekt berechnet wurden (sowohl von als auch von , die die gleiche Funktion repräsentieren - Ausgang von Gate in ) am Gate-Ausgang , und schauen Sie, wie viele Fehler / Fehler für undC N F ( g ) g β C k g D R g C k g D R g C k g C k g D r gDNF(g)CNF(g)gβCgkDgrim Vergleich dazu. Wenn das Gatter eine Konjunktion ist, berechnet der Gatterausgang möglicherweise mehr Eingaben von T0 korrekt (die korrekt berechneten Eingaben von T1 werden jedoch möglicherweise verringert). Für , das als einfache Konjunktion definiert ist, gibt es jedoch bei all diesen Eingaben keine neuen Fehler. Nun ist als ein CNF / DNF-Schalter von , so dass möglicherweise eine Reihe neuer Fehler auf T0 auftreten, die von diesem Schalter ausgehen. Auf T1 gibt es auch keine neuen Fehler auf - jeder Fehler muss an einem der Gate-Eingänge vorhanden sein, und in ähnlicher Weise führt der Schalter auf keine neuen Fehler auf T1 ein. Die Analyse für das ODER-Gatter ist dual.CgkDgrCgkCgkDgr

Die Anzahl der Fehler für die endgültigen Approximatoren ist also durch die Anzahl der Gatter in , multipliziert mit der maximal möglichen Anzahl der Fehler, die von einem CNF / DNF-Schalter (für T0) oder von einem DNF / CNF-Schalter (für T1) eingeführt werden. Die Gesamtzahl der Fehler muss jedoch in mindestens einem Fall "groß" sein (T0 oder T1), da dies eine Eigenschaft von positiven konjunktiven Normalformen mit Klauseln ist, die durch begrenzt sind , was die Schlüsselerkenntnis von Rasborows ursprünglichem Beweis (Lemma) war 5 in der Zeitung von Blum).kβk

Also, was hat Blum getan, um mit Negationen umzugehen (die auf die Ebene der Eingänge gedrückt werden, sodass die Schaltung immer noch nur binäre ODER / UND-Gatter enthält)?β

Seine Idee ist es, CNF / DNF- und DNF / CNF-Schalter nur dann restriktiv vorzubereiten, wenn alle Variablen positiv sind. Dann würden die Schalter genau wie bei Berg und Ulfberg funktionieren und die gleiche Menge an Fehlern verursachen. Es stellt sich heraus, dass dies der einzige Fall ist, der berücksichtigt werden muss.

So folgt er mit einigen Unterscheidungen den Linien von Berg und Ulfberg. Anstatt an jedes Gate der Schaltung , , und , hängt er seine Modifikationen , , und , dh die von ihm definierten "reduzierten" disjunktiven und konjunktiven Normalformen, die sich von undD N F ( g ) C k g D r g g β C N F ' ( g ) D N F ' ( g ) C ' k g D ' R g C N F ( g ) D N F ( g ) C ' r g D ' rCNF(g)DNF(g)CgkDgrgβCNF(g)DNF(g)CgkDgrCNF(g)DNF(g)durch "Absorptionsregel", Entfernen negierter Variablen aus allen gemischten Monomen / Klauseln (er verwendet zu diesem Zweck auch die mit R bezeichnete Operation, wobei einige Monome / Klauseln vollständig entfernt werden; wie wir zuvor besprochen haben, ist seine etwas informelle Definition von R nicht wirklich das Problem , R kann so präzise gemacht werden, dass es an jedem Gatter angelegt wird, aber was entfernt wird, hängt nicht nur von den vorherigen zwei Eingängen ab, sondern von der gesamten Schaltung, die zu diesem Gatter führt, und ihren Approximatoren und , das hat er auch vorgestellt.CgrDgr

In Satz 5 gelangt er zu dem Schluss, dass für eine monotone Funktion reduzierte und in Mengen T1 und T0 am Wurzelknoten (dessen Ausgabe die Ausgabe der gesamten Funktion in ) tatsächlich 1 und 0 berechnen . Dieser Satz ist meines Erachtens richtig. D N F ' g 0 βCNFDNFg0β

Nun kommt das Zählen von Fehlern. Ich glaube, die Fehler an jedem Knoten sollen durch Vergleichen von reduziertem und (die jetzt möglicherweise zwei verschiedene Funktionen sind) mit und wie er sie definierte. Die Definitionen von Approximatoren sind die Papageiendefinitionen von und (Schritt 1), wenn er Variablen mit negierten mischt, aber wenn er sich mit positiven Variablen befasst, verwendet er den Schalter wie im Fall von Berg und Ulfberg (Schritt 2). Und tatsächlich wird er in Schritt 2 die gleiche Anzahl möglicher Fehler wie zuvor einführen (es ist der gleiche Schalter, und alle beteiligten Variablen sind positiv).D N F ' ( g ) C ' r g D ' k g C N F ' D N F 'CNF(g)DNF(g)CgrDgkCNFDNF

Aber der Beweis in Schritt 1 ist falsch. Ich denke, Blum verwechselt , , die tatsächlich, wie er sie definiert hat, von früheren Approximatoren (für Tore , ) mit positiven Teilen von und . Es gibt einen Unterschied, und daher die Aussage " enthält noch alle in enthaltenen Klauseln vor der Approximation des Gatters g, die eine Klausel in oder " verwenden im Allgemeinen falsch.γ 2 h 1 h 2 C N F ' β ( h 1 ) C N F ' β ( h 2 ) C ' g C N F ' β ( g ) γ ' 1 γ ' 2γ1γ2h1h2CNFβ(h1)CNFβ(h2)CgCNFβ(g)γ1γ2

Idolvon
quelle
2
Scheint derselbe Kommentar auf dem RJL-Blog zu sein. rjlipton.wordpress.com/2017/08/17/… hast du das geschrieben? wollte eine Idee hinzufügen: was ist, wenn der Schlüssel T0 / T1 aller gleichen 1-Bit -Wandlung / -Näherung für cnf-dnf zu berücksichtigen ist ? es wird von Berkowitz 1982 bekannt dies ausreichend ist , P vs NP siehe „Komplexität von Schichtfunktionen“ / wegener zu trennen sciencedirect.com/science/article/pii/0304397585902099
VZN
6
@vzn Der Autor dieses Kommentars im Blog ist "vloodin". Der Autor dieser Antwort ist "idolvon". Eine Permutation der Buchstaben gibt einen Hinweis darauf, dass die Autoren nicht zu unterschiedlich sind.
Clement C.
2
Nur neugierig, hat es irgendeine Art von öffentlicher Kommunikation von Blum gegeben, nachdem das Papier in das arxiv hochgeladen wurde?
Matt
9
@Matt Blum hat das Papier zurückgezogen und auf der arXiv-Seite des Papiers den folgenden Kommentar gepostet: "Der Beweis ist falsch. Ich werde genau erläutern, was der Fehler ist. Dafür brauche ich etwas Zeit. Ich werde die Erklärung auf mein Papier setzen Homepage "
Gustav Nordh
Diese Antwort wurde von Scott Aaronson unter Berufung auf andere (nicht genannte) Gutachter als richtig bestätigt: scottaaronson.com/blog/?p=3409
cuniculus
95

Ich kenne Alexander Razborov, dessen bisherige Arbeit äußerst wichtig ist und als Grundlage für Blums Beweis dient. Ich hatte das große Glück, ihn heute kennenzulernen, und verschwendete keine Zeit, um nach seiner Meinung zu dieser ganzen Angelegenheit zu fragen, ob er den Beweis überhaupt gesehen hatte oder nicht, und was dachte er darüber, wenn er es tat.

Zu meiner Überraschung antwortete er, dass er zwar über Blums Artikel Bescheid wusste, es ihm aber zunächst egal war, ihn zu lesen. Mit zunehmender Bekanntheit bekam er jedoch die Gelegenheit, es zu lesen, und entdeckte sofort einen Fehler: Die Argumente von Berg und Ulfberg stimmen perfekt für die Funktion von Tardos, und da dies der Fall ist, ist Blums Beweis notwendig falsch, da dies dem Kern von Satz 6 in seiner Arbeit widerspricht.

Mikhail
quelle
2
Es wäre großartig, wenn Sie dies näher erläutern könnten. Ist bekannt, dass Tardos 'Funktion in P ist?
Thomas
5
Die Tardos-Funktion ist in P und ist eine Annäherung an die Lovasz-Theta-Funktion, die für ein Graphkomplement zwischen der Cliquenzahl und der chromatischen Zahl liegt. Die Lovasz-Theta-Real-Funktion ist eine monotone Funktion eines Graphen. Die Frage ist jedoch, ob diese Annäherung auch zu einer monotonen Funktion eines Graphen führt (nur eine monotone Funktion würde den Beweis ungültig machen). Kann uns jemand den Verweis auf das Tardos-Papier geben, in dem dies definiert ist?
idolvon
7
@idolvon Du meinst das: cs.cornell.edu/~eva/… Es heißt ausdrücklich, dass die Funktion φ eine
polyzeit
12
Vielen Dank! Damit ist es im Grunde genommen erledigt - der Beweis von Bloom muss falsch sein. Nun könnte es interessant sein, einen Fehler zu lokalisieren. Ich werde mich darum kümmern und einen Kommentar zu Lipton abgeben, wie in guten alten Zeiten, so prof. p Spechtwünsche.
Idolvon
1
@idolvon Ja, das dachte ich auch. Blums Argumente sollten die in diesem Artikel definierte Funktion φ übertragen, die besagt, dass monotone und polytime berechenbar sind (trivial durch ihre Definition).
PsySp
41

Dies wird als Community-Antwort gepostet, da (a) dies nicht meine eigenen Worte sind, sondern ein Zitat von Luca Trevisan auf einer Social-Media-Plattform oder von anderen Personen ohne CSTheory.SE-Konto; und (b) jeder sollte sich frei fühlen, dies mit aktualisierten, relevanten Informationen zu aktualisieren.


Zitiert Luca Trevisan aus einem öffentlichen Facebook-Post (14.08.2017) und beantwortet eine Frage zu diesem Artikel von Shachar Lovett :

Die Funktion von Andreev, die eine überpolynomielle Schaltungskomplexität haben soll (Zusammenfassung, dann Abschnitt 7), ist nur eine univariate Polynominterpolation in einem endlichen Feld, das, wenn ich nichts verpasse, durch Gaußsche Eliminierung lösbar ist

Tatsächlich ist dies nicht unbedingt ein Punkt, an dem der Beweis fehlschlägt. Luca antwortete dann auf die folgende Frage (15.08.2017), die sich auf Andrews Kommentar bezog:

Ihr habt recht, Leute, ich habe die Definition von Andreevs Funktion falsch verstanden: Es ist nicht klar, dass sie sich auf Polynominterpolation reduziert


Karl Wimmer kommentierte den von Gustav Nordh angesprochenen Punkt (Wiedergabe mit Karls Erlaubnis):

Ich verstehe nicht, warum wir aus den ersten beiden Absätzen des Beweises von Satz 5 den Schluss ziehen können, dass berechnet . Ich sehe nur eine Art von Einseitigkeit, bei der eine Funktion so berechnet, dass impliziert, dass diese Funktion auch 1 ist.F D N F ' ( g 0 ) f = 1DNF(g0)fDNF(g0)f=1

Der dritte Absatz hilft mir auch nicht: berechnen und sein DNF / CNF-Schalter die gleiche Funktion, aber es folgt nicht unmittelbar, dass der DNF / CNF-Schalter berechnet (weil könnte dies nicht sein, daher können wir keine Rückschlüsse auf Klauseln ziehen.f D N F ' ( g 0 ) fDNF(g0)fDNF(g0)f

(Übrigens: Diese Einseitigkeit entspricht dem obigen Beispiel von Gustav .)

Unter einem anderen Gesichtspunkt könnte ein Standardnetzwerk, das eine monotone Funktion berechnet, sicherlich nicht-monotone Funktionen an internen Knoten berechnen. Theorem 5 gilt nicht für nicht-monotone Funktionen, so möglicherweise nicht richtig berechnet die Unterfunktion in dem Netzwerk , dessen Ausgangsknoten (die für viele nicht-monotone Funktionen geschehen). Aus diesem Grund bin ich nicht davon überzeugt, dass diese induktive Konstruktion von korrekt sein wird.g D N F ' ( g 0 )DNF(g)gDNF(g0)

Wenn ich hier total off-base bin, lass es mich bitte wissen!


Von einem anonymen Benutzer als Reaktion auf Karls Standpunkt:

DNF 'und CNF' sind nur DNF und CNF für f, bei denen Stornierungen von entgegengesetzten Literalen vorgenommen werden, wodurch sie auf eine kürzere Form reduziert werden. Dies wird auch in dem Papier erklärt, und es ist etwas umständlich von der Definition, aber das ist es, was es ist. Satz 5 ist nicht das Problem, Fleisch ist im Satz 6.


Und die Antwort von Karl (die ich hier nochmal wiedergebe):

Ich sehe, was anon sagt (danke!); Mein Kommentar hat meine Verwirrung nicht richtig angesprochen. Wenn monoton ist und bei berechnet , ist es in Ordnung, , die Absorption und den Operator anzuwenden , und der resultierende für . Mit dieser "One-Shot" ist Satz 5 in Ordnung - weiter mit Satz 6. Ich habe diese Definition vonfg0DNF(g0)RDNF(g0)fDNF(g0)

Was ich nicht sehen kann, ist, warum die Gate-by-Gate-Absorption-und- as-you-go-Konstruktion von auf den Seiten 27-28 dasselbe tut. Dies scheint notwendig zu sein, damit die Gate-für-Gate-Analyse in Satz 6 funktioniert, sofern nicht Fehler aufgrund dieser Konstruktion berücksichtigt werden. Ich meine, nicht jede Funktion kann auch durch eine DNF mit Begriffen mit nur nicht negierten oder negierten Literale dargestellt werden, aber für jeden Knoten , scheint immer diese Form zu haben. Was passiert, wenn sich in meinem Netzwerk ein Knoten , für den keine solche Darstellung hat?RDNF(g0)gDNF(g)gres(g)

(Ein weiterer kleiner (?) Punkt: Ich verstehe nicht, was in der Gate-by-Gate-As-You-Go-Konstruktion macht; in 1.-4. Scheint es, als sei bereits die Standard-DNF-Konstruktion, aber mit Absorption und angewendet.)RαR


(Antwort von anon) Ich stimme zu, dass die Unbestimmtheit in der Definition von R ein Problem in Abschnitt 6 sein könnte. R ist nicht explizit definiert, und es sei denn, seine Wirkung hängt in irgendeiner Weise von der gesamten DNF ab (und nicht von den Werten von DNF 'an Toren induktiv). Möglicherweise liegt ein Problem vor. Deolalikars Beweis hatte ein ähnliches Problem - zwei verschiedene Definitionen wurden verwechselt. Hier wissen wir zumindest, was unter DNF zu verstehen ist, und wenn dies die Ursache für das Problem in Abschnitt 6 ist, kann es leicht zu verfolgen sein. Ich bin jedoch noch nicht auf Abschnitt 6 eingegangen, sondern es bedarf eines nachvollziehbaren Beweises durch Approximatoren von Berg und Ulfberg, die in Abschnitt 4 beschrieben sind und sich letztendlich auf Razborovs Konstruktion aus dem Jahr 1985 beziehen, was nicht einfach ist.

Erklärung wie R funktioniert:

Wenn R in einem Schritt angewendet wird, werden nur Terme gelöscht, die in diesem Schritt entgegengesetzte Literale enthalten würden (wir müssen möglicherweise negative Literale verfolgen). Zum Beispiel, lassen Sie uns auswerten als zuerst, um DNF 'am ersten UND-Knoten zu berechnen, erhalten wir bevor wir R anwenden , aber nach dem Anwenden von R verlieren wir das erste aus der ersten Klammer und erhalten (wobei das erste virtuelles NOT haben könnte, wenn wir es verfolgen würden) . Dann wenden Sie das zweite UND an, um zu erhalten

(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
yx
((y)(xy)(y))((xy)(xy)(xy)),
aber dann entfernt R das ganze erste Klammer, weil es praktisch NICHT y vorhanden ist (in diesem Fall mussten wir die vorherigen Schritte nicht verfolgen, aber vielleicht brauchen wir im Allgemeinen), wobei wir oder einfach
((xy)(xy)(xy))
(xy)
Clement C.
quelle
6
Ich bin diesbezüglich skeptisch (benutze aber Facebook nicht, um dort etwas zu sagen) - Andreevs Funktion (im Artikel) wird als zweigeteilte Grafik mit einer linken und rechten Scheitelpunktmenge gleich GF (q) plus einer willkürlichen Kantenmenge angegeben und ein Grad gebunden. Die Frage ist, ob es einen Weg gibt, für jeden Scheitelpunkt auf der linken Seite einen seiner Nachbarn zu wählen, so dass die induzierte Funktion (von links nach rechts) ein Polynom niedrigen Grades ist. Lucas Kommentar trifft zu, wenn wir für jeden linken Scheitelpunkt eine gute Wahl des Nachbarn haben (da es sich dann nur um eine Polynominterpolation handelt), aber mir ist nicht klar, wie ich eine gute Wahl treffen soll.
Andrew Morgan
@ AndrewMorgan Ich habe die CW-Antwort aktualisiert.
Clement C.
@ Karl Wimmer: Bezüglich des Wetters berechnet DNF ′ (g0) f, man muss verwenden, dass f monoton ist, denke ich. In Satz 5 wird angenommen, dass f monoton ist.
Idolvon
verwirrt! zitiert das alles aus dem Facebook-Post? Wenn Sie auf den Facebook-Link shachar lovett oben klicken, sind einige der obigen Antworten für mich sichtbar, andere für mich nicht. zB Karl Wimmer. ist dies auf einige Überprüfungen der Antworten von Freunden auf Facebook zurückzuführen? Wenn ja, ist dies enttäuschend und kein sehr guter Ort für öffentliche Diskussionen. Vielleicht kann jemand einen Screenshot machen? :( oder zitierst du Sachen von außerhalb des Facebook-Posts? Bitte seien Sie vorsichtig / komplett mit Zitaten / URLs
vzn
Oh! Weitere Forschung zitieren Sie auch Antworten von Baez Blog-Post, die Wimmers Antwort usw. enthält johncarlosbaez.wordpress.com/2017/08/15/…
vzn
36

Die Richtigkeit des behaupteten Beweises wird in Luca Trevisans Blog diskutiert: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- np /

Insbesondere hat "anon" den folgenden relevanten Kommentar gepostet:

"Tardos beobachtete, dass die Argumente von Razborov und Alon-Boppana auf eine Funktion übertragen werden, die durch eine nicht monotone Schaltung mit polynomischer Größe berechnet wird (die Funktion ist eine kleine Variante zur Approximation der Lovasz-Theta-Funktion des Graphen). Wenn Berg und Ulfbergs Argumente ebenfalls Wenn Sie sich für die Funktion von Tardos bewerben (was intuitiv wahrscheinlich ist, da ihr Beweis auf Razborovs Beweis zu beruhen scheint), ist es klar, dass die aktuelle Behauptung von Blum nicht richtig sein kann. Leider diskutiert der Autor diesen Punkt nicht. "

Auf eine direkte Frage von "Mikhail" bestätigt Alexander Razborov dies (siehe Mikhail's Post): Die Argumentation von Berg und Ulfberg trifft perfekt auf die Funktion von Tardos zu, und da dies so ist, ist der Beweis von Blum notwendigerweise falsch, da er dem Kern widerspricht des sechsten Satzes in seiner Arbeit. - A. Rasborow

Meiner Meinung nach ist damit definitiv die Frage geklärt, ob das Papier korrekt ist oder nicht (es ist NICHT korrekt!). Es ist auch wichtig zu beachten, dass es schwierig zu sein scheint, den Proof zu reparieren, da die Proofmethode selbst fehlerhaft zu sein scheint.

Update (30.08.2017) Norbert Blum hat auf seiner arXiv-Seite folgenden Kommentar gepostet:

Der Beweis ist falsch. Ich werde genau erläutern, was der Fehler ist. Dafür brauche ich etwas Zeit. Ich werde die Erklärung auf meine Homepage stellen

Gustav Nordh
quelle
3
Ich habe dies als Antwort gepostet, da ich noch keine Berechtigungen zum Posten von Kommentaren habe.
Gustav Nordh
11
Ja, das ist mein Verständnis (aber ich kann mich irren). Die Tardos-Funktion ist eine monotone Funktion, die bei k-Cliquen 1 und bei vollständigen (k-1) -Partit-Graphen 0 ist. Soweit ich das beurteilen kann, verwenden Berg und Ulfberg NUR diese Eigenschaften in ihrem CNF-DNF-Näherungsnachweis für CLIQUE, was beweist, dass Tardos 'Funktion eine exponentielle monotone Komplexität aufweist. Blums Theorem 6 besagt, dass die Untergrenzen der monotonen Komplexität durch CNF-DNF-Näherung für monotone Funktionen dieselbe NICHT-monotone Untergrenze ergeben. Daher hat Tardos 'Funktion eine exponentielle Komplexität gemäß Theorem 6 (was falsch ist).
Gustav Nordh
5
In diesem Fall sieht es so aus, als ob die Klärung dieses Punktes im Moment ein Hauptaugenmerk sein sollte ... Ich glaube nicht, dass ich kompetent oder kompetent genug dafür bin, aber (Daumen drücken, was dem Tippen nicht hilft) andere sind es.
Clement C.
3
Wo ist diese Tardos-Funktion definiert, kann jemand auf das Papier verweisen? Es ist klar, dass nicht-monotone Funktionen, die T0 und T1 trennen, in P existieren (es ist einfach zu konstruieren, zu überprüfen, ob wir einen vollständigen Graphen mit k Knoten haben), aber ist die Tardos-Funktion monoton? Wenn es monoton ist und T0 und T1 trennt, würde es den Beweis ungültig machen. Wenn es jedoch nicht monoton ist, ist der Beweis möglicherweise immer noch richtig.
Idolvon
4
Die Funktion von Tardos wird in ihrem kurzen Artikel definiert, der sich hier befindet: cs.cornell.edu/~eva/… Außerdem werden die Eigenschaften der Funktion von Tardos in [S. Jukna, Boolesche Funktionskomplexität p. 272]
Gustav Nordh
25

Gustav Nordh kommentierte Satz 5 (Seite 29). Speziell die Funktion

(xy)(¬xy)(x¬y)

berechnet die Funktion, die nur , wenn und beide , daher ist sie monoton. Der obige Ausdruck für die Funktion stellt ein "Standardnetz" (wobei die einzigen Negationen ein Literal sind), dessen Knoten den Literalen und , ihren Negationen und jedem der binären Ausdrücke entsprechen. Angenommen, der Ausgabeknoten des Netzwerks heißt .1xy1βxyβg0

Das Blum-Papier erzeugt eine neue disjunktive Normalform aus die zu sein scheintDNFβ(g0)β

xy(xy)

Nach Satz 5 ist nun jedes Monom in ein Implikant von . Aber eines der Monome in ist , was kein Implikant von (weil nicht impliziert ), was dem Theorem widerspricht. Wie in den Kommentaren von Gustav Nordh und der ausführlichen Erklärung von Idolvon erwähnt, wird diese offensichtliche Diskrepanz jedoch durch eine angemessene und weitreichende Auslegung des Begriffs "Ursprung" in der Definition des Reduktionsoperators behoben .DNFβ(g0)fDNFβ(g0)xfx=1f(x,y)=1R

kdog
quelle
2
Es scheint, dass DNF 'für diese Formel (x UND y) ist - bilden Sie die vollständige DNF, stornieren Sie triviale Terme und wenden Sie die Absorption an
idolvon
2
@idolvon Mit der alternativen Definition auf Seite 29 sind Sie richtig. Die Hauptdefinition von jedoch auf den Seiten 27-28. Nach dieser Definition ist die ursprüngliche Analyse von Nordh richtig. Ich werde nicht in der Zeitung herumspringen und nachdenken, was der Autor beabsichtigt hat, insbesondere wenn der Text der Definition auf den Seiten 27-28 in diesem Fall sehr klar ist. Auch für andere Proofs in der Veröffentlichung wird die Definition auf den Seiten DNF
27 bis
2
Die Definition auf den Seiten 27-28 beinhaltet die Verwendung des Operators R, der nicht definiert ist, außer für die vage Formulierung "stammt aus trivialem Monom". Wenn wir das so verstehen, als würde es annulliert, wenn Literale bis zu diesem Zeitpunkt beibehalten würden, dann sind die Definitionen dieselben. In jedem Fall benötigen Sie EINIGE Interpretationen für R. Da R in Kapitel 6 so wichtig ist, ist die richtige Interpretation wichtig, und es gibt tatsächlich eine, die induktiv ist.
Idolvon
2
Wenn R in einem Schritt angewendet wird, werden nur Terme gelöscht, die in diesem Schritt entgegengesetzte Literale enthalten würden (möglicherweise müssen negative Literale verfolgt werden). Zum Beispiel, lassen Sie uns auswerten als zuerst, um DNF 'am ersten UND-Knoten zu berechnen, erhalten wir bevor wir R anwenden , aber nach dem Anwenden von R verlieren wir das erste aus der ersten Klammer und erhalten
(xy)(¬xy)(x¬y)
((xy)(¬xy))(x¬y)
(xy)((xy)(yy))
x
(y)(xy)(y),
idolvon
2
(wobei das erste virtuelles NOT haben könnte, wenn wir es verfolgen würden). Wenden Sie dann das zweite UND an, um aber dann entfernt R die gesamte erste Klammer, weil sie virtuell NICHT y enthält (in diesem Fall mussten wir die vorherigen Schritte nicht nachverfolgen, aber vielleicht brauchen wir sie im Allgemeinen) und lässt oder einfachyx
((y)(xy)(y))((xy)(xy)(xy)),
((xy)(xy)(xy))
(xy)
idolvon
17

Könnte man die Listendecodierung von Reed-Solomon-Codes verwenden, um zu zeigen, dass Andreevs POLY-Funktion in P steht, ähnlich wie es Sivakumar in seinem vergleichbaren Artikel über Mitglieder getan hat ? Oder ist die POLY-Funktion als NP-vollständig bekannt?

Lance Fortnow
quelle
10
Lance, ich kann deine Fragen nicht beantworten. Im Juni 1986 fragte David Johnsons "Offenes Problem des Monats", ob Andreevs Problem NP-vollständig ist. Siehe Davids Spalte zur NP-Vollständigkeit im Journal of Algorithms 7: 2, S. 289-305. Ich bin mir nicht sicher, ob es jemals eine Lösung gab.
Ravi Boppana
1
Johnsons Artikel aus dem Jahr 1986 geht den polynomiellen Rekonstruktionstechniken und Listendecodierungsergebnissen der 90er Jahre voraus.
Lance Fortnow
1
Hier ist meine Idee unter Verwendung der Notation in Abschnitt 7 von Norbert Blums Artikel. Ein Polynom p, das eine Lösung für das POLY-Problem darstellt, könnte als Reed-Solomon-Codewort angesehen werden. Wählen Sie eine Funktion f aus, indem Sie zufällig eine Kante aus jedem Scheitelpunkt in A auswählen. Damit sollte f mit p in deutlich mehr als einem 1 / q-Bruchteil der Eingaben übereinstimmen. Dann können wir die Listendecodierung auf f verwenden, um eine polynomiell lange Liste von Möglichkeiten für p zu erstellen, und wir können jede von ihnen überprüfen.
Lance Fortnow
1
Wenn ich Ihren Algorithmus nicht falsch verstehe, kann man mit dem Guruswami-Sudan-Algorithmus eine Liste dekodieren, wenn die Anzahl der Vereinbarungen mindestens , wobei der Grad von ist und wir an dem Fall interessiert sind wenn , was bedeutet, dass wir viel mehr als eine -Fraktionsvereinbarung benötigen . dpdqddp 1dqlogq1q
4
@Matt Unter der Annahme, dass ich das Obige richtig gelesen habe, ist diese Funktion diejenige, für die Blum behauptet, die Komplexität der Superpolynomschaltung bewiesen zu haben. Wenn es sich jedoch in P befindet, muss es eine Polynomkreiskomplexität aufweisen, was dem angeblichen P vs. NP-Beweis widerspricht.
Clement C.
14

Er hat sein arXiv aktualisiert, um zu sagen, dass sein Beweis falsch ist:

Der Beweis ist falsch. Ich werde genau erläutern, was der Fehler ist. Dafür brauche ich etwas Zeit. Ich werde die Erklärung auf meine Homepage stellen.

Mehrdad
quelle
9

Lipton und Regans Blog hier enthält eine nette Diskussion auf hoher Ebene mit einem interessanten Kommentar zur Beweisstruktur.

Sie weisen auch darauf hin, dass Blums Stammbaum eine niedrigere Grenze für die Komplexität der Booleschen Schaltkreise darstellte, die mehr als 30 Jahre bestand. Dies ist natürlich nur eine "Nebeninformation", da Experten den Beweis bereits ernsthaft untersuchen.

kodlu
quelle
3

Auch hier: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Zitat von Alon Amit:

(persönliche Meinung, 14. August, später am Tag): Ich glaube nicht, dass dieses Papier einer Prüfung standhält. Ein tiefgreifender Satz, der ebenso gründlich erforscht wurde wie P ≠ NP, wird aller Wahrscheinlichkeit nach mit tiefgreifenden und weitreichenden neuen Techniken gelöst. Es ist nicht unmöglich, dass es mit einer leichten Verbesserung bekannter, vorhandener Methoden gelöst wird, aber es ist nur sehr, sehr, sehr unwahrscheinlich.

Jack
quelle
11
Das ist kein Argument (eine gültige Meinung und eine, die ich zugeben muss, dass ich sie teile, aber kein gültiges Argument, von dem ich glaube, dass wir es hier haben sollten). Diese Art von Dingen ist schon einmal passiert .
Clement C.
8
Ja, ich habe nichts gestritten. Beantworten Sie einfach die Frage "Wo wird dieses Papier besprochen?" Und fassen Sie die besagte Diskussion bis zu diesem Punkt zusammen.
Jack
2

Es ist unwahrscheinlich, dass dies aus folgendem Grund zutrifft: Die Annäherungsmethode ist allgemein genug, dass jede untere Schranke mit ihr bewiesen werden kann. Dies ist ein Ergebnis aufgrund von Razborov. Warum ist das ein Problem? Da dies bedeutet, dass die Methode der Annäherung nicht der Hauptfortschritt ist, kann sie alles ausdrücken, das Fleisch wird woanders sein. Es scheint kein solches Fleisch in der Zeitung zu geben, was darauf hindeutet, dass der Autor höchstwahrscheinlich einen subtilen Fehler begeht, die Art von Fehler, die vor dem Auge verborgen ist, aber im Wesentlichen eine Annahme ist, die die Antwort impliziert. Für diejenigen, die keine Komplexitätstheoretiker sind: Dies ist ein sehr guter Geruchstest. Es ist genauso wahrscheinlich, dass jemand behauptet, in einer Woche eine Rakete in seinem Keller zu bauen, um zum Mond zu fliegen.

Wo ist also dieser subtile Fehler? Auf Trevisans Blog gibt es einen Kommentar von Lovett, der diese versteckte Annahme in Satz 6 nahe legt.

Skeptiker
quelle
schöner / relevanter Punkt; fyi razborovs "no go" (1989) people.cs.uchicago.edu/~razborov/files/approx.pdf, aber ich glaube, dieser Beweis ist nicht sehr gut analysiert. Man muss sorgfältig verstehen, ob die angegebenen Bedingungen über die bloßen Worte "Annäherungsmethode" hinausgehen, die seit ihrer Entstehung durch Rasborov durch Überarbeitungen / Entwicklungen / Verfeinerungen usw. gegangen ist. Diese genauen Bedingungen werden von späteren Forschern anscheinend nicht viel analysiert. Die andere große Barriere ist die von Rasborow / Rudich (natürliche Beweise). en.wikipedia.org/wiki/Natural_proof
vzn
Abgestimmt, weil der Inhalt dieser Antwort bereits in früheren Antworten angesprochen wurde.
Überprüfung
-2

Blum verwendet Razborovs Näherungsmethode, um zu schließen, dass eine Funktion in in nicht berechnet werden kann .PNPcP

Das Ziel der Razborovschen Näherungsmethode ist es zu zeigen, dass nicht berechnen kann , wobei eine Boolesche Funktion ist und beliebige Schaltung von Gattern ist.f f C mCffCm

Eine Boolesche Funktion hat nur eine Wahrheitstabelle, aber keinen einzigen algebraischen Ausdruck, und ein Problem hat auch nur eine Boolesche Funktion, die es löst.

Einige (möglicherweise alle) Funktionen sind isomorph (Probleme gibt es nicht).

Um zu dem Schluss zu kommen, dass nach Rasborovs Aproximationsmethode ist, muss bewiesen werden, dass eine Schaltung mit Gattern (wie ist polinomisch in Bezug auf die Einträge von ) keine Funktion ohne Isomorphime berechnen kann ist der minimale Isomorphismus.m m f f fNP=Pmmfff

Ixer
quelle