Wie beweise

Mir ist bewusst, dass dies eine sehr dumme (oder zu naheliegende) Frage ist. Irgendwann bin ich jedoch verwirrt.

Wir können zeigen, dass P NP$=$ genau dann ist, wenn wir einen Algorithmus entwerfen können, der ein gegebenes Problem in NP in polynomialer Zeit löst .

Ich verstehe jedoch nicht, wie um alles in der Welt wir beweisen können, dass P NP . Bitte entschuldigen Sie mich für das folgende Gleichnis, da es so irrelevant sein könnte, aber jemandem zu sagen, dass er beweisen soll, ob P nicht gleich NP ist, erscheint mir so, als würde er jemandem sagen, dass er beweisen soll, dass Gott nicht existiert.$\neq$

Es gibt eine Reihe von Problemen, die mit nicht deterministischen endlichen Automaten (NFA) mit einer polynomiellen Anzahl von Zuständen unabhängig von der aktuellen Technologie nicht gelöst werden können (ich weiß, dass dies eine schlampige Definition ist). Darüber hinaus gibt es eine beträchtliche Anzahl von Algorithmen, die einige entscheidende Probleme (kürzester Pfad, minimaler Spannbaum und sogar die Summe der Ganzzahlen ) bei Problemen mit der Polynomzeit verursachen.$1 + 2 + \dots + n$

Meine Frage in Kürze: Wenn ich glaube, dass P NP$=$ , würden Sie sagen "dann zeigen Sie Ihren Algorithmus, der ein NP- Problem in Polynomialzeit löst !". Angenommen, ich glaube P NP . Was würden Sie dann genau fragen? Was soll ich zeigen?$\neq$

Die Antwort lautet eindeutig "Ihr Beweis". Was für ein Beweis zeigt jedoch, dass ein Algorithmus nicht existieren kann? (in diesem Fall ein polynomieller Zeitalgorithmus für ein NP- Problem)

Mir sind drei Hauptgründe bekannt, die beweisen könnten, dass P$\,\neq\,$NP .

1. $\Omega(n\log n)$$n$$O(n^c)$$c$Schaltungskomplexität ist eine andere.

2. Zeigen, dass P und  NP unterschiedliche Struktureigenschaften haben. Zum Beispiel wird P  unter Komplementierung geschlossen. Wenn Sie diesen NP zeigen könnten$\,\neq\,$co-NP (dh, dass NP  nicht durch Komplementierung geschlossen wird), dann muss P sein$\,\neq\,$NP . Dies treibt das Problem natürlich nur eine Ebene tiefer - wie würden Sie diesen NP beweisen ?$\,\neq\,$Co-NP ?

   $\exists\mathrm{SO}$

3. Beweisen Sie, dass ein Problem nicht NP- vollständig ist. Wenn P$\,=\,$$\emptyset$$\Sigma^*$ $\,\neq\,$NP .

Meine Frage in Kürze: Wenn ich glaube, dass P = NP , würden Sie sagen "dann zeigen Sie Ihren Algorithmus, der ein NP- Problem in Polynomialzeit löst !".

Vergessen Sie nicht, dass Sie immer noch nachweisen müssen, dass Ihr Algorithmus das Problem löst und in polynomialer Zeit abläuft.

Angenommen, ich glaube P ≠ NP . Was würden Sie dann genau fragen? Was soll ich zeigen?

Versuchen Sie zunächst zu erklären, "warum" P ≠ NP und warum dieser Grund verwendet werden kann, um P ≠ NP in einem geeigneten logischen Rahmen zu beweisen . Skizzieren Sie dann einen Beweis und erklären Sie, wie seine zweifelhaftesten Teile verteidigt werden können. Teilen Sie diesen Beweis anschließend in einfachere Aussagen auf, die unabhängig überprüft werden können.

• Zum Beispiel ist das von ZFC bereitgestellte logische Gerüst ein guter (in gewissem Sinne sogar zu guter) Beweis für die Existenz von Modellen (von explizit gegebenen Mengen von Axiomen, die häufig sogar zusätzliche metallogische Eigenschaften erfüllen). Wenn Sie also einen Grund für P ≠ NP kennen, der mit der Existenz eines Modells mit einigen merkwürdigen Eigenschaften zusammenhängt, erklären Sie diesen Grund und zeigen Sie dann, wie das entsprechende Modell innerhalb von ZFC konstruiert werden kann.
• Als Nichtbeispiel glaube ich, dass ein Grund, warum P P NP ist, darin besteht, dass die Mathematik nahezu alles approximieren kann, was in der physikalischen Welt vorkommt, einschließlich der Zufälligkeit. Es ist jedoch bekannt, dass formale Systeme nur sehr begrenzt in der Lage sind, eine bestimmte Zeichenfolge, Zahl, ein "Objekt" oder ein "Artefakt" als im Wesentlichen zufällig zu beweisen. Daher ist es unwahrscheinlich, dass dieser Grund für einen Beweis herangezogen werden kann in jedem explizit gegebenen deterministischen formalen System. Wenn Sie ein probabilistisches (Quanten-) Beweissystem entworfen haben, können Sie bestimmte Beweise im System möglicherweise nur bis zu einer endlichen Wahrscheinlichkeit in Abhängigkeit von Ihren verfügbaren physischen Ressourcen verifizieren ...
• Als wahrscheinliches Nichtbeispiel spiegelt das Gesetz der ausgeschlossenen Mitte im Grunde genommen eine statische Sicht des (mathematischen) Universums wider und ist daher in einem dynamischen Universum äußerst unwahrscheinlich . Nun wäre NP = coNP (oder irgendein anderer Zusammenbruch der Polynomhierarchie ) im Grunde genommen eine ungefähre Version des Gesetzes der ausgeschlossenen Mitte in Bezug auf die Zeitkomplexität, aber die Zeitkomplexität ist einem dynamischen Universum zu nahe, als dass dies möglich wäre. Es gibt logische Rahmenwerke wie Girards lineare Logik, die dynamische Aspekte des Universums erfassen können. Beachten Sie jedoch, dass sich Brouwer in einer ähnlichen Situation befand und bereits in seiner Eröffnungsrede Intuitionismus und Formalismus das notwendige Scheitern von Hilberts Programm als Tatsache bezeichnet hat im Jahr 1912 (Erklärung, warum es Zirkelschluss sein würde), war aber noch nicht einmal in der Lage, Gödels Unvollständigkeitsbeweis von 1930 zu skizzieren.
• Als ein ungefähres Beispiel wollen wir versuchen, einige der verfügbaren Beweise für P ≠ NP zu erfassen , nämlich die exponentielle Untergrenze für das Polytop des Handlungsreisenden und die mangelnde Eignung auflösungsbasierter Verfahren für die Erfüllbarkeit aufgrund von Prinzipien der schwachen Einstecktiefe. Das "Warum" in diesem Fall ist, dass eine bestimmte Klasse von NP-vollständigen Problemen nicht effizient durch Algorithmen gelöst werden kann, die auf bestimmten natürlichen (für die Klasse der betrachteten NP-vollständigen Probleme) Prinzipien beruhen, wie lineare Programmierformulierungen für TSP oder auf Auflösungsbasis Beweismethoden für SAT. Verschiedene Artikel gaben unterschiedliche unabhängige Gründe an, warum dies verwendet werden könnte, um etwas zu beweisen. Der letzte Artikel über TSP führte beispielsweise eine "enge Verbindung zwischen semidefiniten Programmierreformulierungen von LPs und Einweg-Quantenkommunikationsprotokollen" als Grund an, während der letzte Artikel über die Auflösung zwei unabhängige Gründe angeführt, nämlich Untergrenzen "für eine Klasse von Formeln, die das Pigeonhole-Prinzip darstellen, und für zufällig erzeugte Formeln".
  Sie können auch beobachten, dass es Versuche gab, die Ergebnisse im Laufe der Zeit zu verbessern. Die anfänglichen Ergebnisse für TSP betrafen nur die symmetrische lineare Programmierformulierung, während die neuesten Ergebnisse keine solche Einschränkung aufweisen und zusätzlich zu TSP auch für die Probleme mit maximalem Schnitt und maximalem stabilem Satz gelten. Die ersten Ergebnisse für die Auflösung betrachteten nur grundlegende Davis-Putnam-Auflösungsverfahren und eine einzelne Klasse künstlicher Gegenbeispiele, während die neuesten Ergebnisse große Klassen auflösungsbasierter Methoden abdecken und mehrere Klassen natürlich vorkommender Gegenbeispiele angeben.
  Für TSP habe ich keine Ahnung, wie die Ergebnisse weiter gestärkt werden sollten, außer vielleicht, indem neben TSP, maximaler Schnitt und maximaler stabiler Satz weitere Probleme angesprochen werden. Zur Lösung hätte ich viele Ideen, wie ich die Ergebnisse weiter verbessern könnte, aber der Artikel, auf den ich verweise, stammt aus dem Jahr 2002. Stephen Cook und Phuong Nguyen haben 2010 eine Monografie Logical Foundations of Proof Complexity veröffentlicht, die ich nicht einmal durchgesehen habe Ich schätze, es wird bereits viele meiner Ideen abdecken. Es ist interessant festzustellen, wie wenig es für die meisten von uns tatsächlich von Bedeutung ist, wie sehr sich diese Ergebnisse im Laufe der Zeit trotz unseres Interesses am P ≠ NP verbessert habenFrage. Selbst wenn in der Zwischenzeit bewiesen worden wäre, dass Algorithmen, die auf logischen Systemen ohne ein Äquivalent der Cut-Regel beruhen, die Erfüllbarkeitsprobleme nicht effizient lösen können, würden wir dennoch glauben, dass es bei P ≠ NP im Wesentlichen keine Fortschritte gegeben hat , dass das Problem im Wesentlichen besteht immer noch so weit offen wie immer.