Wenn P = NP, könnten wir Beweise für die Goldbachsche Vermutung usw. erhalten?

Dies ist eine naive Frage, aus meiner Erfahrung heraus; Entschuldigung im Voraus.

Goldbachs Vermutung und viele andere ungelöste Fragen in der Mathematik können als kurze Formeln in Prädikatenrechnung geschrieben werden. Zum Beispiel Cooks Artikel "Können Computer routinemäßig mathematische Beweise entdecken?" formuliert diese Vermutung als

\forall n [(n > 2 \land 2 | n) \supset \exists r \exists s (P (r) \land P (s) \land n = r + s)]

$\forall n [( n > 2 \wedge 2 | n) \supset \exists r \exists s (P(r) \wedge P(s) \wedge n = r + s) ]$

Wenn wir die Aufmerksamkeit auf polynomial lange Beweise beschränken, dann sind Theoreme mit solchen Beweisen in NP. Wenn also P = NP ist, können wir bestimmen, ob zB die Goldbachsche Vermutung in der Polynomzeit wahr ist.

Meine Frage ist: Könnten wir auch in polynomialer Zeit einen Beweis vorlegen?

Bearbeiten . Nach den Kommentaren von Peter Shor und Kaveh hätte ich meinen Anspruch begründen müssen, dass wir feststellen könnten, ob die Vermutung von Goldbach wahr ist, wenn es sich tatsächlich um einen der Sätze mit einem kurzen Beweis handelt. Was wir natürlich nicht wissen!

cc.complexity-theory proof-complexity automated-theorem-proving proof-search Joseph O'Rourke
quelle

Um einen kurzen (<1000 Seiten?) Beweis für Goldbachs Vermutung zu liefern, muss es zunächst einen kurzen Beweis geben. P = NP hat darauf keinen Einfluss.

Peter Shor

@ Suresh, @Kaveh: Du scheinst das falsch zu verstehen. Hier haben wir ein konkretes Beispiel eines NP-Suchproblems. Der hier relevante Quantifikator ist das Vorhandensein eines Beweises (in einem geeigneten formalen System) des Theorems.

Kristoffer Arnsfelt Hansen

Eine andere Bemerkung ist, dass wir tatsächlich einen Algorithmus aufschreiben können, der, wenn P = NP, einen Beweis für eine gegebene Aussage findet, wenn er in der Länge der Aussage und der Länge des kürzesten Beweises in einem Zeitpolynom existiert. (Dieses Polynom ist eine Grenze, die für alle Theoreme gilt.) Es wird jedoch ein "astronomischer" Algorithmus sein.

Kristoffer Arnsfelt Hansen

@ Joe: Nein, ich kann den Algorithmus jetzt tatsächlich aufschreiben! (Auch wenn man nicht weiß, ob P = NP ist). Die Idee ist, was als Levins universelle Suche bekannt ist.

Kristoffer Arnsfelt Hansen

@Kristoffer: Cool! Wusste nichts über LS. Ich sehe, dass Marcus Hutter eine Art Verbesserung von LS hat: "Der schnellste und kürzeste Algorithmus für alle genau definierten Probleme." Internationales Journal der Grundlagen der Informatik, 13 (3): 431-443, 2002.

Joseph O'Rourke

Antworten:

Tatsächlich!

Wenn P = NP, können wir nicht nur entscheiden, ob es einen Beweis der Länge n für die Goldbachsche Vermutung (oder eine andere mathematische Aussage) gibt, sondern wir können ihn auch effizient finden!

Warum? Weil wir fragen können: Gibt es einen Beweis, der von dem ersten Bit abhängig ist, das ... ist, dann gibt es einen Beweis, der von dem ersten Bit abhängig ist, das ... ist, und so weiter ...

Und woher wüsstest du n? Sie probieren einfach alle Möglichkeiten in aufsteigender Reihenfolge aus. Wenn wir einen Schritt in der i'ten Möglichkeit machen, versuchen wir auch einen Schritt in jeder der Möglichkeiten 1 .. (i-1).

Dana Moshkovitz
quelle

Ist das nicht Levins universeller Suchalgorithmus?

Mohammad Al-Turkistany

@turkistany: ja, das ist es!

Dana Moshkovitz

Dana hat die Frage beantwortet. Aber hier sind einige Kommentare zur praktischen Seite.

$P=NP$ $P=NP$ $P=coNP$

$NP$ $l$ $P=NP$ $l$

$P=NP$ $l$ $l$ $P=NP$ $P$ $DTime(n^2)$ ), dann kann man diesen Algorithmus nehmen und nach Beweisen von praktikabler, aber sehr großer Länge suchen, die größer sein werden als alle Beweise, die ein Mensch jemals finden kann, und wenn der Algorithmus keine Antwort findet, dann die Satz ist praktisch unmöglich zu beweisen. Der Trick, den Dana erwähnt hat, wird auch hier funktionieren, um den Beweis zu finden.

Aus praktischen Gründen:

$P=NP$ $DTime(10000n^{10000})$
es wird nur dann einen Beweis finden, wenn es einen gibt (dh der Satz ist in ZFC kein unentscheidbarer Satz), außerdem sollte der Beweis möglichst kurz sein.
$P\neq NP$ $NP=DTime(n^{\log^* n})$

Kaveh
quelle