Reduktion von P gegen NP auf SAT

12

Die folgende Frage verwendet Ideen aus der Kryptographie, die auf die Komplexitätstheorie angewendet werden. Es handelt sich jedoch um eine rein komplexitätstheoretische Frage, für deren Beantwortung keinerlei Kryptowissen erforderlich ist.

Ich schreibe diese Frage bewusst sehr informell. Mangels Details wird es möglicherweise etwas falsch angegeben. Bitte zögern Sie nicht, auf die Korrekturen in Ihren Antworten hinzuweisen.


In der folgenden Zeitung:
Nicht formbare Kryptographie, Danny Dolev, Cynthia Dwork und Moni Naor, SIAM Rev. 45, 727 (2003), DOI: 10.1137 / S0036144503429856 ,
schreiben die Autoren:

Angenommen, die Forscherin A hat einen Beweis erhalten, dass P ≠ NP ist, und möchte diese Tatsache Professor B mitteilen. Angenommen, A beweist, um sich zu schützen, ihren Anspruch auf B auf eine wissensfreie Weise ...

Es gibt mehrere Standard-NP-vollständige Probleme, wie Erfüllbarkeit (SAT), Graph-Hamiltonicity und Graph-3-Colorability (G3C), für die es keine wissensbasierten Beweise gibt. Die Standardmethode zum Beweisen eines NP-Theorems besteht darin, es zunächst auf eine Instanz der oben genannten NP-vollständigen Probleme zu reduzieren und dann den Null-Wissens-Beweis durchzuführen.

Diese Frage betrifft eine solche Reduzierung. Angenommen, P vs. NP wird auf eine der folgenden Arten abgerechnet:

  • P = NP
  • P ≠ NP
  • P vs. NP ist unabhängig von der axiomatischen Standardsatztheorie.

Sei σ der Beweis. Dann ist P vs. NP in einer NP- Sprache (da es einen kurzen Beweis dafür gibt). Die Reduktion vom Satz (sagen wir P ≠ NP) zum NP-vollständigen Problem (sagen wir SAT) ist unabhängig von σ. Das ist:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

Das ist weit jenseits meiner Vorstellungskraft! Es scheint, dass es unwahrscheinlich ist, dass wir eine solche Formel ϕ konstruieren können, selbst wenn wir den Beweis σ erhalten.

Könnte jemand etwas Licht ins Dunkel bringen?

Außerdem sei L eine NP-Sprache, in der P gegen NP liegt. Die Sprache besteht aus unendlich vielen Theoremen wie P vs. NP beliebiger Größe.

Was ist ein Kandidat für L?
Kann L NP-vollständig sein?

MS Dousti
quelle
Ich verstehe diesen Teil nicht: "Sei σ der Beweis. Dann ist P gegen NP in NP (da es einen kurzen Beweis dafür gibt). Die Reduktion vom Satz (sagen wir P ≠ NP) zum NP -Vollständiges Problem (sagen wir SAT) ist unabhängig von σ. Das heißt: Es gibt eine Formel ϕ, die genau dann erfüllt werden kann, wenn P ≠ NP ist. " Könnten Sie es bitte etwas näher erläutern? Es macht für mich keinen Sinn, dass "P vs NP in NP ist", auch wenn Sie es in "Gibt es einen Längennachweis von höchstens n in Theorie T für P \ neq NP" ändern? Entweder gibt es ein kleinstes n, es gibt einen Beweis dieser Größe für die Frage, oder es gibt keinen solchen Beweis.
Kaveh
1
φnφTφ
φPNPT
@Kaveh: Klarstellung hinzugefügt.
MS Dousti
Einige interessante Ideen, aber es macht keinen Sinn zu sagen, dass ein "Beweis in NP ist" oder dass "es einen kurzen Beweis gibt". Das heißt, es könnte eine Methode geben, um diese Parallelen herzustellen, aber sie müsste formeller definiert werden. Das, was diesen Ideen am nächsten kommt, scheint der Rahmen für natürliche Beweise von Razborov / Rudich zu sein.
vzn

Antworten:

20

Die Möglichkeit, das Testen einer mathematischen Aussage (z. B. eine Auflösung von P gegen NP) als eine Frage der Form "ist Formel .. erfüllbar" anzusehen, ist die folgende:

Korrigieren Sie ein Axiomensystem. Wenn eine Zeichenfolge der Länge n ein Beweis für die mathematische Aussage im Axiomensystem ist, kann man dies auf einfache Weise definieren: Die Zeichenfolge sollte aus Sätzen bestehen. Jeder Satz sollte entweder ein Axiom sein oder aus den vorhergehenden Sätzen durch eine der Inferenzregeln folgen.

Es ist kein Problem, eine Boolesche Formel zu definieren, die all dies überprüft. Alles was Sie wissen sollten ist die Länge n des Beweises!

Dana Moshkovitz
quelle
9

P vs. NP ist in NP (da es einen kurzen Beweis dafür gibt)

Das macht für mich nicht viel Sinn. NP ist eine Komplexitätsklasse für Entscheidungsprobleme mit beliebig großen Instanzen, und P vs. NP hat sie nicht. Nach dem, was Sie später sagen:

sei L eine NP-Sprache, in der P gegen NP liegt.

Sie können stattdessen bedeuten, dass P vs. NP ein Beispiel für ein NP-Problem ist. aber natürlich ist es das! Es ist auch ein Beispiel für eine unendliche Anzahl von P-, DTIME (n) usw.-Problemen. Insbesondere sind hier zwei DTIME (1) -Kandidaten für L, von denen genau einer richtig ist: immer zurückkehren true; oder immer zurückkehren false.

Alexey Romanov
quelle
2
Bitte lesen Sie die Randnotiz am Anfang der Frage noch einmal. Ich habe das informell formuliert, und das führt zu Ihrer Verwirrung. Um zu formalisieren, muss man eine Verallgemeinerung des Theorems "P vs. NP" in Betracht ziehen. Für unendlich viele n nimmt die Verallgemeinerung einen Satz der Länge n an. Aus den Theoremen entsteht eine Sprache L, die in DTIME (1) unmöglich entschieden werden kann.
MS Dousti
Dann ist ein kurzer Beweis / Widerspruch von "P gegen NP" nur eine Instanz von "verallgemeinertem P gegen NP" (vielleicht eine einfache?), Und es folgt nicht, dass GPvNP in NP ist.
Alexey Romanov
Abgestuft: Ich verstehe den Einwand gegen die Formulierung der ersten zitierten Aussage, da Mitglieder von NP Mengen sind und "P vs. NP" keine Menge ist. Beim zweiten Einwand ist jedoch jedes "NP-Problem" ein Entscheidungsproblem, das immer rechtmäßig so formuliert werden kann, dass entschieden wird, ob eine Zeichenfolge in einer Sprache vorliegt. Ich sehe nichts Falsches an seiner Definition von L. Außerdem ignoriert der Appell an triviale, immer wahre oder immer falsche DTIME (1) -Sprachen den Punkt: Wenn wir bereits ALLE wahren Aussagen kennen, bauen wir vermutlich einen Look auf. Aufwärtstisch für die Turing-Maschine, um auf konstante Zeit zuzugreifen.
Daniel Apon
[Fortsetzung] Angenommen, L ist eine richtige Sprache (dh eine unendliche Menge), dann nehmen Sie eine unendlich große Tabelle mit "wahren Aussagen" an, auf die zugegriffen werden kann, was gegen alle Arten von Regeln zu verstoßen scheint. Oder mehr auf den Punkt gebracht: Warum verallgemeinert sich Ihr Argument für DTIME (1) nicht auf JEDE Sprache, nicht nur auf die seltsame, die wir gerade in Betracht ziehen?
Daniel Apon
1
LDTIME(1)