Wie kann man P = NP nicht lösen?

96

Es gibt viele Versuche, entweder oder zu beweisen, und natürlich denken viele Leute über die Frage nach und haben Ideen, um beide Richtungen zu beweisen.PN PP=NPPNP

Ich weiß, dass es Ansätze gibt, die erwiesenermaßen nicht funktionieren, und es gibt wahrscheinlich noch mehr, die in der Vergangenheit gescheitert sind. Es scheint auch so genannte Barrieren zu geben , die viele Beweisversuche nicht überwinden können.

Wir wollen vermeiden, nach Sackgassen zu suchen. Was sind sie?

Raphael
quelle
16
Ich denke, das ist besser, um Community-Wiki zu sein (da es keine eindeutige Antwort auf diese Frage gibt, ist sie zu weit gefasst).
6
@ SaeedAmiri Nein. Das Community-Wiki war früher ein Alibi, um Fragen zuzulassen, die für die Stack Exchange-Plattform nicht geeignet waren. Dies wird jedoch nicht mehr durchgeführt .
Gilles
4
Hinweis für Moderatoren: Diese Frage ist umfassender als eine normale Stapelaustauschfrage, wir versuchen jedoch, ein kanonisches Frage-Antwort-Paar zu erstellen. Wenn Sie der Meinung sind, dass diese Frage in der vorliegenden Form nicht existieren sollte, diskutieren Sie sie bitte auf unserer Meta-Site .
Gilles
für eine ähnliche Frage von der entgegengesetzten / konstruktiven Seite sehen Sie, wie Informatiktheorien und -anfragen gelöst werden können?
vzn
4
Wag antworte: arXiv ist eine Schatzkammer von Möglichkeiten, dies nicht zu tun.
Pseudonym

Antworten:

76

Ich würde sagen, die bekanntesten Hindernisse für die Lösung von sindP=NP

  1. Relativierung (wie von Ran G. erwähnt)
  2. Natürliche Beweise - Unter bestimmten kryptographischen Voraussetzungen haben Rudich und Rasborow bewiesen, dass wir mit einer Klasse von Beweisen beweisen können, die natürliche Beweise genannt werden.PNP
  3. Algebrization - von Scott Aaronson und Avi Wigderson. Sie beweisen, dass Beweise, dass Algebrisierung und nicht trennen kannN PPNP

Eine andere, die ich kenne, ist das Ergebnis, dass keine LP-Formulierung TSP lösen kann (von Yannakakis für symmetrische LPs bewiesen und erst kürzlich auf allgemeine LPs ausgeweitet). Hier ist ein Blog-Beitrag, in dem das Ergebnis besprochen wird.

Opt
quelle
4
Relevante Links: zu Barrieren im Allgemeinen und zu Spielzeugbeispielen . Außerdem sollten Sie mit Ihrem letzten Satz vorsichtig sein. Ich denke, es wäre ratsam, einen Link zum Blogeintrag einzuschließen, der erklärt, warum das mit allgemeinen LPs nicht machbare TSP-Ergebnis nicht beweist , da die Leute dadurch verwirrt sein könnten die Tatsache, dass LP vollständig ist. PPNPP
Artem Kaznatcheev
1
Wenn Sie die Antwort verbessern möchten (sie ist noch nicht ganz akzeptabel), fügen Sie bitte kurze Erklärungen und Links zu Details hinzu, damit der neugierige Leser weiß, wovon Sie sprechen.
Raphael
57

Hinweis: Ich habe die Antwort noch nicht sorgfältig geprüft und es fehlen noch Teile. Betrachten Sie sie als ersten Entwurf.

Diese Antwort richtet sich hauptsächlich an Personen, die keine Forscher in der Komplexitätstheorie oder verwandten Bereichen sind. Wenn Sie ein Komplexitätstheoretiker sind und die Antwort gelesen haben, lassen Sie es mich bitte wissen, wenn Sie ein Problem bemerken oder eine Idee zur Verbesserung der Antwort haben.

Wo Sie behauptete Lösungen von P gegen NP finden

Andere Listen, wie man P gegen NP nicht löst

Lance Fortnow, Sie glauben also, Sie hätten P verus NP , 2009, erledigt

Scott Aaronson, Acht Zeichen Ein behaupteter PPP-Beweis ist falsch , 2010

Polymath-Seite für Deolalikars Artikel , wo der Abschnitt mit den weiteren Lesungen eine schöne Liste von Referenzen zum Problem enthält.


Wie man sich P vs. NP nicht nähert

Lassen Sie mich diskutieren, "wie man sich P vs. NP nicht nähert ", und zwar nicht im Sinne von Ideen, die nicht funktionieren, sondern im allgemeineren Sinne. P vs. NP ist ein leicht zu formulierendes Problem (siehe auch meine Antwort hier ):

NP = P: Für jedes Entscheidungsproblem mit einem Polynomzeitprüfalgorithmus gibt es einen Polynomzeitalgorithmus.

oder äquivalent

Es gibt einen polynomialen Zeitalgorithmus für SAT.
SAT kann durch jedes andere NP-vollständige Problem ersetzt werden .

.

Oft vereinfachen und überphilosophisieren Menschen das Problem und übertreiben die praktische Bedeutung des Problems (wie oben angegeben). Solche Aussagen sind oft als Anschauung gedacht, ersetzen aber keinesfalls die eigentliche mathematische Aussage über das Problem.

Theoretische Effizienz ist nicht dasselbe wie Machbarkeit in der Praxis.

Lassen Sie mich zunächst mit übertriebenen praktischen Konsequenzen.

I. Es ist möglich, dass P = NP, aber es hilft in der Praxis bei keinem Problem!

2264n65536+22128

nlglgn

lgn>62

Der Hauptpunkt hierbei ist, dass P ein abstraktes einfaches Modell für eine effiziente Berechnung ist, und dass die Komplexität im schlimmsten Fall ein abstraktes einfaches Modell für die Schätzung der Kosten einer Berechnung ist wie die in (I) oben als effizienter Algorithmus wirklich. P ist ein schönes abstraktes Modell, es hat schöne Eigenschaften, es macht technische Probleme leicht und es ist nützlich. Wie jede mathematische Abstraktion verbirgt sie jedoch Details, die uns in der Praxis interessieren könnten. Es gibt verschiedene weiterentwickelte Modelle, aber je komplizierter das Modell wird, desto weniger schön wäre es, darüber zu streiten.

In der Praxis geht es den Menschen darum, eine Antwort auf das Problem für Fälle zu berechnen , in denen sie Wert auf einen angemessenen Ressourcenverbrauch legen. Es sind aufgabenabhängig und sollten berücksichtigt werden.

Der Versuch, bessere Algorithmen für praktische Fälle von NP-schwierigen Problemen zu finden, ist ein interessantes und würdiges Unterfangen. Es gibt heuristische SAT-Solver-Algorithmen, die in der Industrie verwendet werden und praktische SAT-Instanzen mit Millionen von Variablen lösen können. Es gibt sogar einen internationalen SAT-Wettbewerb .

(Aber es gibt auch kleine konkrete Fälle, in denen alle diese Algorithmen versagen und ganz schlimm versagen. Wir können tatsächlich beweisen, dass alle modernen SAT-Löser exponentiell viel Zeit benötigen, um einfache Fälle wie das Propositional Pigeonhole Principle zu lösen .)

Beachten Sie, dass Korrektheit und Laufzeit von Programmen nicht nur durch Ausführen des Programms auf Instanzen erzielt werden können . Es spielt keine Rolle, wie viele Instanzen Sie versuchen, keine Menge ist ausreichend. Es gibt unendlich viele Eingabemöglichkeiten und Sie müssen für alle die Richtigkeit und Effizienz (dh die Laufzeit ist polynomiell) des Programms nachweisen. Kurz gesagt, Sie benötigen einen mathematischen Beweis für die Richtigkeit und Effizienz. Wenn Sie nicht wissen, was ein mathematischer Beweis ist, sollten Sie zunächst einige Grundkenntnisse in Mathematik erwerben (lesen Sie ein Lehrbuch Diskrete Mathematik / Kombinatorik / Graphentheorie; dies sind gute Themen, um zu erfahren, was als mathematischer Beweis gilt).

Seien Sie auch vorsichtig mit anderen Behauptungen über P vs. NP und der Konsequenz seiner Antworten. Solche Behauptungen beruhen oft auf ähnlichen Vereinfachungen.

Komplexitätstheoretiker interessieren sich nicht wirklich für eine Antwort auf P vs. NP!

Ich habe ein bisschen übertrieben. Natürlich interessiert uns eine Antwort auf P vs. NP. Aber wir kümmern uns darum in einem Kontext. P vs. NP ist unser Hauptproblem, aber es ist nicht das ultimative Ziel. Es ist ein leicht zu formulierendes Problem, es beinhaltet viele grundlegende Ideen, es ist nützlich, um die Art von Fragen, die uns interessieren, Leuten zu erklären, die mit dem Thema nicht vertraut sind. Aber wir suchen keine ein-Bit-Ja / Nein-Antwort auf die Frage.

Wir bemühen uns um ein besseres Verständnis der Art der effizienten Berechnung . Wir glauben, dass die Lösung der Frage mit einem solchen Verständnis einhergeht, und das ist der wahre Grund, warum uns das wichtig ist. Es ist Teil einer Vielzahl von Forschungsarbeiten. Wenn Sie einen Vorgeschmack auf das haben möchten, was wir tun, schauen Sie sich ein gutes Lehrbuch zur Komplexitätstheorie an, z. B. Aroras und Baraks " Komplexitätstheorie: Ein moderner Ansatz " ( Entwurfsversion ).

Kurz gesagt, aus der Perspektive eines Komplexitätstheoretikers

P vs. NP ist kein Puzzle mit einer Ja / Nein-Antwort. Wir suchen nach einer Antwort auf P vs. NP, weil wir glauben, dass dies zu einem besseren Verständnis der Natur effizienter Berechnungen führen wird. Eine Antwort ohne wesentliche Verbesserung unseres Verständnisses ist nicht sehr interessant.

Es hat zu viele Fälle gegeben, in denen Nicht-Experten Lösungen für P vs. NP behaupteten, und diese Behauptungen leiden typischerweise unter Problemen, die sie nicht gemacht hätten, wenn sie nur ein Standardlehrbuch zur Komplexitätstheorie gelesen hätten.

Häufige Probleme P = NP

Die Behauptungen von P = NP scheinen häufiger zu sein. Ich denke, das Folgende ist der häufigste Typ. Jemand hat eine Idee und schreibt ein Programm und testet es an einigen Instanzen. Er glaubt, es sei Polynomzeit und löst ein NP-vollständiges Problem korrekt. Wie ich oben erklärt habe, zeigt keine Testmenge P = NP. P = NP braucht einen mathematischen Beweis , nicht nur ein Programm, das ein NP-vollständiges Problem in der Polynomzeit zu lösen scheint .

Diese Versuche leiden normalerweise unter einem der beiden Probleme:

I. Der Algorithmus ist nicht wirklich polynomial.

II. Der Algorithmus löst nicht alle Instanzen korrekt.

[geschrieben werden]

So stellen Sie sicher, dass Ihr Algorithmus nicht wirklich funktioniert

Sie können durch Testen nicht nachweisen, dass Ihr Algorithmus ordnungsgemäß funktioniert. Aber Sie können zeigen, dass es nicht richtig funktioniert, indem Sie testen! So können Sie sicherstellen, dass Ihr Algorithmus nicht korrekt ist, wenn Sie bereit sind, etwas zu tun.

Schreiben Sie zunächst ein Programm zum Konvertieren von SAT-Instanzen (im Standard-CNF-Format) in das NP-harte Problem, das Sie lösen. SAT ist eines der am häufigsten untersuchten NP-schwierigen Probleme, und die Reduktion von anderen Problemen auf SAT ist normalerweise einfach. Nehmen Sie zweitens die Beispiele, mit denen die modernen SAT-Löser zu kämpfen haben (z. B. die Beispiele aus dem SAT-Wettbewerb), und geben Sie sie an Ihren Algorithmus weiter, um zu sehen, wie Ihr Algorithmus funktioniert. Probieren Sie bekannte harte Instanzen wie das Propositional Pigeonhole Principle (und betrügen Sie nicht, indem Sie sie als Sonderfälle fest codieren), kryptografische Instanzen (wie RSA Factoring Challenges ), zufällige k-SAT-Instanzen in der Nähe des Schwellenwerts usw. aus.

10n2

Wie Sie Ihre algorithmische P = NP- Idee überprüfen können, funktioniert nicht

Wenn Sie dies tun, werden Sie ziemlich sicher sein, dass Ihr Algorithmus nicht funktioniert (wenn er besser als die hochmodernen SAT-Löser funktioniert, nehmen Sie am nächsten Wettbewerb teil und viele Leute wären daran interessiert, Ihren Algorithmus und Ihre Ideen zu studieren).

Jetzt wissen Sie, dass es nicht wirklich funktioniert, aber das ist nicht genug. Sie wollen wissen warum,

Ist der Grund, warum mein Algorithmus nicht funktioniert, ein kleines Problem, das behoben werden kann, oder gibt es einen fundamentalen Grund, warum er nicht funktioniert?

Manchmal ist das Problem mit dem Algorithmus einfach und man kann identifizieren, was konzeptionell falsch war. Das beste Ergebnis ist, dass Sie den Grund verstehen, warum Ihre Idee nicht funktionieren kann. Oft ist es nicht der Fall, Ihre Idee funktioniert nicht, aber Sie können nicht herausfinden, warum. In diesem Fall ist Folgendes zu beachten:

zu verstehen, warum eine Idee nicht funktionieren kann, kann schwieriger sein als das Lösen von P vs. NP!

Wenn Sie Ihre Idee ausreichend formalisieren können, können Sie möglicherweise Einschränkungen bestimmter Ideen nachweisen (z. B. gibt es Ergebnisse, die besagen, dass bestimmte Formalisierungen des Greedy-Algorithmus NP-vollständige Probleme nicht lösen können). Es ist jedoch noch schwieriger, und Sie haben keine großen Chancen, wenn Sie kein Standardlehrbuch zur Komplexitätstheorie gelesen haben.

Manchmal gibt es nicht einmal eine klare konzeptionelle Idee, warum der Algorithmus funktionieren sollte, dh er basiert auf einigen nicht gut verstandenen Heuristiken . Wenn Sie keine klare Vorstellung davon haben, warum Ihr Algorithmus funktionieren sollte, haben Sie möglicherweise keine große Chance, zu verstehen, warum dies nicht der Fall ist!

Problem 1: Der Autor kennt die Definition von P und NP nicht oder versteht noch schlimmer nicht, was ein mathematischer Beweis ist. Da dem Autor die mathematische Grundausbildung fehlt, versteht er nicht, wenn ihm gesagt wird, was er vorlegt, dass dies kein Beweis ist (z. B. folgen die Schritte nicht aus den vorherigen).

Ausgabe 2: Der Autor verwechselt "Wir wissen nicht wie" mit "mathematischer Unmöglichkeit". Zum Beispiel gehen sie von verschiedenen ungerechtfertigten Annahmen aus und werden gefragt, warum diese Aussage wahr ist. sie antworten "wie kann es falsch sein?". Es ist häufig anzunehmen, dass ein Programm, das das Problem löst, bestimmte Schritte ausführen muss, z. B. bestimmte Zwischenwerte berechnen muss, weil es sich keine alternative Lösung für das Problem vorstellen kann.

[zu vervollständigen]

[geschrieben werden]

Wenn eine Forderung nicht unter diesen grundlegenden Problemen leidet, wird die Ablehnung schwieriger. Auf der ersten Ebene kann man einen falschen Schritt im Argument finden. Die typische Antwort des Autors ist, dass ich es reparieren kann und dies hin und her kann weitergehen. Ähnlich wie bei P = NP-Lösungen ist es häufig sehr schwierig, ein grundlegendes Problem mit einer Idee zu finden, das zeigen kann, dass es nicht funktioniert, insbesondere wenn die Idee selbst informell ist.

Kaveh
quelle
So sehr ich die P-versus-NP-Seite mag, finde ich es ärgerlich, dass nicht nachverfolgt wird, welche Beweise von ihren Autoren zurückgezogen wurden. Für einige der arXiv-Links finden Sie explizite Hinweise zu "Dieses Papier wurde zurückgezogen" auf arXiv. Ich bin mir ziemlich sicher, dass es mehr zurückgezogene Beweise gibt als nur die ArXiv-Papiere mit ausdrücklicher Ankündigung. OK, mir ist bewusst, dass zurückgezogene Proofs nicht überbewertet werden sollten, da das Zurückziehen eines "früheren Proofversuchs" nicht bedeutet, dass dieselben Autoren es später nicht erneut versuchen. Das Schweigen über zurückgezogene Beweisversuche vermittelt jedoch immer noch einen voreingenommenen Eindruck.
Thomas Klimpel
@ Thomas wenige der "Kurbel" -Autoren "ziehen" jemals ihre Papiere zurück. der unausgesprochene punkt der woegorgi-liste ist, dass sie deutlich weniger qualität hat als arxiv- papiere . aber ich bin damit einverstanden, wünschte, woegorgi könnte einige zusätzliche infos hinzufügen und etwas flexibler in seiner bearbeitung sein. Zum Beispiel hat er meine P-gegen-NP-Gliederung nicht in die Liste aufgenommen, obwohl er kürzlich einen weiteren Punkt auf dem Fukuyama-Proof gepostet hat, der mit einem langen cstheory.se-Chat zusammenhängt.
vzn
1
Ich weiß es zu schätzen, dass du das noch einmal besuchst! Scheint, als hätte ich das Kopfgeld vorzeitig der falschen Person zugeteilt. ;) Beachten Sie, dass Sie stackedit.io verwenden können, um einen Beitrag im Laufe der Zeit vorzubereiten. Freue mich auf den Rest der Post!
Raphael
34

Möglicherweise ist die häufigste Technik, die nicht verwendet werden kann, die Relativierung , dh ein TM mit Oracle-Zugriff.

ABPA=NPAPBNPB

PNPOPONPOA

P=?NP

Ran G.
quelle
1
Nur um dies vollständig zu korrigieren, bedeutet Diagonalisierung hier eine direkte einfache Diagonalisierung. Siehe diese Frage
Kaveh
1
Relativierung ist also nicht die Beweismethode, sondern der Effekt, der einen Beweis bricht? Können Sie ein Beispiel für einen Beweis nennen / verlinken, der relativiert werden kann?
Raphael
2
ja, Relativierung ist keine Beweismethode, sondern eine Eigenschaft eines Beweises (hier übrigens nicht formal). Wenn der Proof unverändert funktioniert, wenn alle Turingmaschinen durch Orakelmaschinen ersetzt werden, wird der Proof relativiert. Sie können sich beispielsweise davon überzeugen, dass sich der Beweis des Zeithierarchiesatzes in diesem Sinne relativiert.
Sasho Nikolov
10

Ich würde vorschlagen, diesen Blog-Beitrag von Lance Fortnow zu lesen :

  1. Sie glauben also, Sie hätten P verus NP beigelegt. Sie liegen falsch. Finde es heraus. Manchmal können Sie immer noch etwas Interessantes aus Ihrem fehlerhaften Beweis retten.
  2. Sie glauben, der Beweis ist richtig. Dein Glaube ist falsch. Gehen Sie zurück zu Schritt 1.
  3. Nehmen Sie Annahmen oder Verknüpfungen vor, auch wenn diese scheinbar klein und offensichtlich sind? Verwenden Sie Wörter wie "deutlich", "offensichtlich", "leicht zu sehen", "sollte", "muss" oder "wahrscheinlich"? Sie behaupten, die vielleicht wichtigste Frage in der gesamten Mathematik zu klären. Man kann keine Annahmen treffen. Gehen Sie zurück zu Schritt 1.
  4. nk
  5. Sie reichen Ihre Arbeit in einem Online-Archiv ein. Vielleicht erzählen Ihnen einige Leute, was in Ihrer Zeitung fehlt oder falsch ist. Dies sollte dazu führen, dass Sie mit Schritt 1 fortfahren. Stattdessen nehmen Sie einige bedeutungslose Änderungen an Ihrem Papier vor und veröffentlichen es erneut.
  6. Irgendwann ignorieren die Leute dein Papier. Sie wundern sich, warum Sie nicht Ruhm und Reichtum bekommen.
  7. Sie reichen Ihre Arbeit in einer Zeitschrift ein.
  8. Das Papier wird abgelehnt. Wenn Sie klug wären, würden Sie zu Schritt 1 zurückkehren. Wenn Sie klug wären, wären Sie niemals zu Schritt 7 gekommen.
  9. Sie beschweren sich beim Herausgeber, dass der Herausgeber den Beweis entweder nicht versteht oder dass er leicht zu beheben ist. Sie sind schockiert, dass ein seriöser Redakteur oder eine seriöse Zeitschrift Ihre Arbeit auf diese Weise behandeln würde.
  10. Sie reichen das Papier erneut ein, legen Berufung ein und versuchen es mit anderen Zeitschriften, ohne Erfolg.
  11. Sie sind überzeugt, dass "das Establishment" Ihr Papier absichtlich unterdrückt, weil unser Fachgebiet viel weniger interessant werden würde, wenn wir das P-gegen-NP-Problem lösen und es daher um jeden Preis offen halten müssen.
  12. Wenn ich dir etwas anderes sage, würdest du mir glauben?
Kaveh
quelle
7
In der Frage wird nach Ansätzen gefragt, die erwiesenermaßen nicht funktionieren, und nach Ansätzen, die in der Vergangenheit gescheitert sind. In dieser Antwort wird kein Ansatz erwähnt.
Tsuyoshi Ito
6
Mein Punkt ist, dass es sinnlos ist, die Frage zu kopieren und einzufügen, da der Blog-Beitrag sie überhaupt nicht beantwortet.
Tsuyoshi Ito
7
Dies beantwortet die Frage in der Tat nicht . Der Blogpost ist eine knifflige Liste von Schritten, die das typische P = NP? Kurbel geht durch. Während ich unterhalte, liefert mir dies keine spezifischen Theorien , von denen gezeigt wurde, dass sie P und NP nicht trennen (oder kollabieren) können.
Raphael
4
Wie wäre es damit? Diese Frage fragt nach Hemmnissen für den Nachweis von P! = NP. Die Barrieren in dieser Antwort (wie in den Kommentaren angegeben) sind "etwas annehmen", "schlechte Interpretation", "etwas sagen ist klar", "an etwas glauben". Diese Barrieren sind zu allgemein, da sie Hindernisse für den Nachweis von irgendetwas darstellen und nicht spezifisch Hindernisse für den Nachweis von P! = NP.
Tyson Williams
1
In den gültigen Kommentaren fehlt ein grundlegender Punkt. Der Blog wurde von Lance Fortnow verfasst, einem Experten für Komplexitätstheorie und Weltautorität in diesem Bereich. Er hat gerade ein neues Buch über P vs NP Golden Ticket herausgebracht . so spricht er grundsätzlich aus eigener erfahrung.
VZN
2

Hier ist ein etwas obskurer / tiefer / schwieriger / Insider-Blickwinkel / Bezugspunkt / Wendung in Bezug auf Ansätze über Schaltkreise aus den 1980er Jahren, auf die ich vor Jahren von Luca Trevisan an anderer Stelle im Cyberspace hingewiesen und von Stasys Jukna, Autor eines hervorragenden, wiederholt wurde Referenz in der Nähe des Themas, Boolean Function Complexity: Advances and Frontiers (Algorithmen und Kombinatorik, Band 27 ).

man kann einen früheren Trend in einigen von Rasborovs Überlegungen erkennen, der schließlich zum Natural Proofs- Papier führte (sogenannte "Einbürgerung"). ref [273] ist sehr technisch und schwierig und scheint von späteren Veröffentlichungen / Büchern kaum zitiert, erweitert oder wiederholt zu werden, obwohl Natural Proofs als eine spätere große Verallgemeinerung angesehen werden könnten. Der Auszug ist von John E Savages ausgezeichnete Referenzmodelle der Berechnung p457

Ω(n2)n

[270] AA Razborov, „Niedrigere Schranken für die monotone Komplexität einiger boolescher Funktionen“, Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801 (in russischer Sprache); Englische Übersetzung in sowjetischer Mathematik. Dokl. 31 (1985), 354–357

[271] AA Razborov, „Eine niedrigere Grenze für die monotone Netzwerkkomplexität der logischen bleibenden Karte“, Mat. Zametki 37 (1985), 887–900 (in russischer Sprache); Englische Übersetzung in Mathe. Notes 37 (6) (1985), 485–493.

[273] AA Razborov, "Über die Methode der Annäherung", Proc. 21. Ann. ACM Symp. Theory of Computing (1989), 167–176.

vzn
quelle
2
Ich verstehe nicht, wie dies die Frage "wie man P nicht beweist? = NP" beantwortet. Im Moment scheint es eher eine Art Spekulation über die Gedanken von jemandem zu sein.
Juho
2
Klar, ich schlage nur vor, dies alles explizit zu machen. Die Schaltungskomplexität ist nicht einmal ein Material für Anfänger, daher ist ein gewisser Hintergrund gerechtfertigt. Es ist zu erwarten, dass der Leser kein Experte in der Komplexitätstheorie ist.
Juho
@juho ok. Als ich das Savage-Buch [das sehr "schaltungsorientiert" ist] sah, das in einer Klasse für Anfänger verwendet wurde, überraschte es mich auch. stimmte seinem fortgeschrittenen Material daher der Formulierung des 1. Satzes zu. Was "Spekulationen über Gedanken" betrifft, gibt es keine, es sei denn, Razborovs eigene Gedanken werden so zitiert, wie sie in seinen eigenen Papieren geschrieben / aufgezeichnet sind.
VZN
1
und im Übrigen ist dies insgesamt eine sehr fortgeschrittene Frage (nicht wirklich Bachelor-Niveau) und andere Antworten sind fortgeschritten und liegen im Allgemeinen außerhalb des Bachelor-Niveaus.
vzn