Liste von Theoremen, die besagen, dass P genau dann nicht gleich NP ist, wenn

18

Ich halte es für eine gute Idee, eine Liste von Theoremen zu erstellen, aus denen hervorgeht, dass P nicht gleich NP ist, wenn und nur wenn ein und derselbe existiert, eine Komplexitätsklasse in einer anderen Komplexitätsklasse enthalten ist und so weiter und so fort.

cc.complexity-theory big-list p-vs-np Tayfun Pay
quelle

15

Das wäre ein konstanter Bruchteil aller Komplexitätspapiere!

MCH

5

Ich würde sagen: "Liste der Bedingungen, die P? NP implizieren", da nicht alle diese Sätze "genau dann" sind. Ich denke, die Leute sind im Allgemeinen mehr daran interessiert zu wissen, wie man P? NP beweist, indem man etwas anderes beweist, als die vielen Konsequenzen dieses Ergebnisses aufzulisten, ein Thema, das an anderer Stelle viel diskutiert wurde.

Janoma

2

@Janoma: Wenn Sie sich auf Implikationen beschränken möchten, wird die Liste angesichts der enormen Anzahl von Ergebnissen der Form sehr umfangreich sein: "Wenn P! = NP, dann kann das Problem X nicht innerhalb eines konstanten Faktors genau / approximiert gelöst werden in polynomialer Zeit ". Die Frage sollte viel gezielter oder besser formuliert werden, wenn wir das vermeiden wollen.

Anthony Labarre

4

@Janoma: Das löst Anthonys begründete Sorge nicht. Hypothesen, die P = NP implizieren, sind einfach Negationen der Konsequenzen von P ≠ NP, und Hypothesen, die P ≠ NP implizieren, sind Negationen der Konsequenzen von P = NP. Wenn SAT in Polynomzeit lösbar ist, dann ist P = NP. Ist Max3SAT innerhalb eines konstanten Faktors von weniger als 8/7 polynomial-zeitlich approximierbar, so ist P = NP. Und so weiter.

Tsuyoshi Ito

7

@Janoma: "Wenn X dann P = NP" ist das gleiche wie "Wenn P ≠ NP dann nicht-X".

Jeffs

11

Hier ist eine Eins:

Mahaneys Theorem: Es gibt keine spärliche NP-Komplettmenge, wenn und nur wenn (unter Karp-Reduktion). $P \ne NP$

Ein anderer ist:

genau dann, wenn $P \ne NP$ $P \ne PH$

Mohammad Al-Turkistany
quelle

Möglicherweise ist dies einfach:

genau dann, wenn

.

P \neq N P

$P \ne NP$

F P \neq F N P

$FP \ne FNP$

Mohammad Al-Turkistany

11

genau dann, wenn Einwegfunktionen im ungünstigsten Fall existieren. $P \ne NP$

Referenz:

Alan L. Selman. Ein Überblick über Einwegfunktionen in der Komplexitätstheorie. Mathematical Systems Theory, 25 (3): 203–221, 1992.

Mohammad Al-Turkistany
quelle

1

Ein

Schiedsrichter

B P P \neq N P

$BPP \neq NP$

Ja, ich bin sicher. :) Siehe die Referenz.

Mohammad Al-Turkistany

8

Hier ist ein Ergebnis der deskriptiven Komplexitätstheorie:

$P \ne NP$

Referenz: Immerman, Sprachen, die Komplexitätsklassen erfassen

Mohammad Al-Turkistany
quelle

... auf geordneten Strukturen. Ansonsten wissen wir uneingeschränkt, dass solche Eigenschaften vorliegen.

Emil Jeřábek unterstützt Monica am

@ EmilJeřábek ja, zu geordneten Strukturen, wie sie von Immerman implizit in obigem Papier angenommen wurden.

Mohammad Al-Turkistany

7

Der Ladner-Satz kann wie folgt ausgedrückt werden:

$P \ne NP$ $NP-P$

$NP$

Referenz

Komplexitätstheorie und Kryptologie: Eine Einführung in die Kryptokomplexität Von Jörg Rothe, Seite 106

Mohammad Al-Turkistany
quelle

Liste von Theoremen, die besagen, dass P genau dann nicht gleich NP ist, wenn

Antworten: