Überprüfen Sie meinen Beweis, dass Co-NP!= P

Question

Dies ist Hobby-Level-Arbeit, nicht meinen Job. Ich habe diesen Auszug mit geschrieben, um einige Ideen über Co-NP zu teilen.

Die Idee ist, eine Problemkategorie in CO-NP auszuwählen, in der die richtige Antwort aufgrund der Schaltungskomplexität schwer zu überprüfen ist, um ihn als 1-in-k-SAT-Formel auszudrücken, und zeigen Sie dort auch ein kurzes Zertifikat, dessen Die Länge in Bits ist genau die Anzahl der Klauseln. Es ist möglicherweise wahr oder falsch, dass alle CO-NP-Probleme in diesem Formular ein so kurzes Zertifikat haben (CO-NP?= NP), aber ich zeige, dass unabhängig davon das Kurzzertifikat für dieses Problem willkürlich schwer gemacht werden kann Finden Sie aufgrund der verschachtelten Beziehung mit NP. Grundsätzlich möchte ich eine bestimmte kreisförmige Abhängigkeit zwischen den Orakles von NP und CO-NP hervorheben. Das Argument, gegen CO-NP= P zu stampfen, ist, dass kein TM hoffen kann, das Problem der Suche nach dem Kurzzertifikat in subberechtiger Zeit anzugreifen, da die Art und Weise, wie ich das Problem definiere, eine beliebige Menge an "eigentlichen Zufall" enthält. Grundsätzlich ist es ein spezifisches Rezept, um ein "Monster" -Ko-NP-Problem aus einem einfachen Zertifikat aufzubauen.

Jetzt habe ich viele Fragen für jeden, der mit formellerem Training ist als ich:

.
• wurde diese Problemkategorie mit einem anderen Namen ausgedrückt?
• ist das ein offensichtliches totendes oder unerforscht?
• Wie kann ich die gleichen Ideen ausdrücken, aber offizieller gegen TM-Fähigkeiten?

Answer 1

wtlu ist in p.

Algorithmus:

• Machen Sie die 1-in-k-Sat-Formel-Monoton, indem Sie eine Klausel für jedes Paar von Literalen (x + ~ x)= 1 hinzufügen und ~ x mit einer neuen Variablen ersetzen.
• Wählen Sie einen großen Prime P aus, zumindest größer als die Anzahl der Klauseln.
• Drehen Sie die 1-in-K-Sat-Formel in ein System der linearen Gleichungen Modulo p.Jede ursprüngliche Klausel in der Form (x, y, z ...)= 1 wird zu einer Gleichung (x, y, z ...)= 1 mod p.
• Führen Sie Gaußsche Elimination aus.
Wenn die Formel eine WTL-Instanz war, wird ein Widerspruch vor der Erreichung von Zeilen-Echelon-Form in Form einer widersprüchlichen Gleichung 0= k mod p (mit k!= 0) erreicht.

warum es funktioniert:

Wenn es zwei Sätze von Klauseln gibt, die den gleichen Satz von Literalen abdecken, so dass (C1 + C2 + C3 ...)= X und (C1 '+ C2' + C3 '...)= Y und X!= Y, dann ist es auch der Fall Modulo p.Somit ist das System der Gleichungen Modulo P auch nicht erfüllt.

Answer 2

Hier ist ein Gegenargument. Eine ähnliche Proofstruktur konnte leicht verwendet werden, um zu beweisen, dass XOR-SAT schwer ist.

.

1. Nehmen Sie eine unzufriedene XOR-SAT-Formel mit einem großen Raum. Sie können es nicht mit einem auflösenden Algorithmus lösen.

2. Es gibt jetzt ein kurzes Unzufriedenheitszertifikat, da XOR-SAT in P.

ist

3. Wenn Sie keine Eliminierung wissen, kombinieren Sie zufällige Klauseln zusammen, bis zwei Klauseln die gleichen Variablen haben, eine Reihe entspricht Null und die andere Reihe entspricht einem. Futter ist ein besonderer Fall, wo die Klauseln keine gemeinsamen Literatur haben.

4. Fügen Sie der XOR-SAT-Formel zufällige Klauseln und Variablen hinzu, um es schwieriger zu machen, die Dinge zufällig Dinge zu tun.

Aber in Wirklichkeit können Sie in einer Polynommenge und des Raums Gaußsche Ausscheidung machen, bis sich zwei Reihen gegenseitig aufheben, um 0= 1 zu erzeugen.

Um Ihr Argument zu erweitern und interessant zu gestalten, müssen Sie zumindest zeigen, dass es einen grundlegenden Unterschied mit XOR-SAT gibt, denn ein Anfang ist, dass es keinen Prozess gibt, der dem Eliminierung ähnlich ist, wo Sie die Variablen nacheinander herausnehmen können während des Prozesses der Isolierung der 2 Konfliktensätze von Klauseln, während die zusätzlichen Informationen ignoriert werden.