Anweisungen, die implizieren

Dies ist eine Art offene Frage, für die ich mich im Voraus entschuldige.

Gibt es Beispiele für Aussagen, die (scheinbar) nichts mit Komplexität oder Turing-Maschinen zu tun haben, deren Antwort aber implizieren würde ?$\mathbf{P}\neq \mathbf{NP}$

Ein Beweissystem für die Aussagenlogik heißt polynomisch begrenzt , wenn jede Tautologie einen Beweis im System des Längenpolynoms in der Länge von .$\varphi$$\varphi$

Die Aussage "Es gibt kein polynomial beschränktes " entspricht nach einem klassischen Ergebnis von Cook und Reckhow , impliziert also .P ≠ N $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Die geometrische Komplexitätstheorie (GCT) (auch [1]) wurde noch nicht erwähnt. Es ist ein großes ehrgeiziges Programm, um P vs NP mit algebraischer Geometrie zu verbinden. zB eine kurze Zusammenfassung der Umfrage zum Verständnis des Mulmuley-Sohoni-Ansatzes für P vs. NP , Regan:

Stabilität ist informell ein Begriff, nicht „chaotisch“ zu sein, und hat sich unter dem leitenden Einfluss von DA Mumford unter anderem zu einem Hauptzweig der algebraischen Geometrie entwickelt. Ketan Mulmuley und Milind Sohoni [MS02] stellen fest, dass viele Fragen zu Komplexitätsklassen als Fragen zur Art von Gruppenaktionen auf bestimmte Vektoren in bestimmten Räumen umgewandelt werden können, die Probleme in diesen Klassen codieren. In dieser Umfrage werden die Rahmenbedingungen aus der Sicht von Laien erläutert und versucht zu bewerten, ob dieser Ansatz den Angriffen auf die Frage von P. vs. NP wirklich neue Kraft verleiht.

auch eine kurze Zusammenfassung im Abschnitt "Eine neue Hoffnung?" im Status des P vs NP-Problems , Fortnow (2009)

Mulmuley und Sohoni haben eine Frage zur Nichtexistenz von Polynomzeitalgorithmen für alle NP-vollständigen Probleme auf die Frage nach der Existenz eines Polynomzeitalgorithmus (mit bestimmten Eigenschaften) für ein bestimmtes Problem reduziert. Dies sollte uns auch angesichts der Probleme (1) - (3) Hoffnung geben.

Trotzdem glaubt Mulmuley, dass es ungefähr 100 Jahre dauern wird, dieses Programm durchzuführen, wenn es überhaupt funktioniert.

[1] Erklärung der geometrischen Komplexitätstheorie im Wikipedia-Stil (tcs.se)

Das folgende Ergebnis von Raz (Elusive Functions und Lower Bounds for Arithmetic Circuits, STOC'08) zielt auf (und nicht direkt auf P ≠ N P ) ab, könnte aber für das OP nahe genug sein:$VP\neq VNP$$P\neq NP$

Ein Polynom-mapping ist , ( s , r ) -elusive, wenn für jedes Polynom-mapping Γ : F s → F m der Grad r , Bild ( f ) ⊄ Bild ( Γ ).$f:\mathbb F^n \to \mathbb F^m$$(s, r)$$Γ : \mathbb F^s → \mathbb F^m$$r$$f$$\not⊂$$Γ$

Für viele Einstellungen der Parameter , explizite Konstruktionen schwer fassbar Polynom-mappings implizieren stark (bis exponentiell) untere Schranken für die allgemeinen Rechenschaltungen.$n, m, s, r$

Es gibt ein neueres Gebiet der Komplexität, das als Graphkomplexität bezeichnet wird und untersucht , wie größere Graphen aus kleineren Graphen unter Verwendung von UND- und ODER-Verknüpfungen von Kanten aufgebaut werden. Jukna hat eine schöne Umfrage . Insbesondere unter Verwendung von Einheiten von "Sterngraphen" gibt es einen Schlüsselsatz, siehe Bemerkung 1.18 (der Satz ist technisch stärker als unten und impliziert tatsächlich ):$P \ne NP/poly$

Wir wussten bereits (Satz 1.7), dass bipartite Graphen G der Sternkomplexität S t a r ( G ) = ( n m / log n ) existieren; In der Tat sind dies fast alle Graphen. Andererseits impliziert das starke Vergrößerungs-Lemma, dass sogar eine Untergrenze von S t a r ( G ) ≥ ( 2 + c ) n für eine willkürlich kleine Konstante c > 0 für die Sternkomplexität eines expliziten $n × m$$Star(G) = (nm/ \log n)$$Star(G) ≥ (2+c)n$$c > 0$ Graph G mit m = o ( n ) hätte große Konsequenzen für die Schaltungskomplexität: Ein solcher Graph würde eine explizite Boolesche Funktion f G ergeben, die eine Schaltung mit Exponentialgröße (in der Zahl log 2 n m Variablen)erfordert! (Denken Sie daran, dass für boolesche Funktionen noch keine superlinearen Untergrenzen bekannt sind.) Insbesondere, wenn der Graph G so ist, dass die Nachbarschaft von Eckpunkten in G durch eine nicht deterministische Turing-Maschine bestimmt werden kann, die im Zeitpolynom in läuft die binäre Länge l o g $n×m$$G$$m = o(n)$$f_G$$\log_2 nm$$G$$G$ der Codes von Eckpunkten, dann eine untere Schranke S t eine r ( G ) ≥ ( 2 + c ) n für eine beliebig kleine Konstante c > 0 würde bedeutendass P ≠ N P . Die Sternenkomplexität von Graphen erfasst somit eines der grundlegendsten Probleme der Informatik.$log_2 n$$Star(G) ≥ (2 + c)n$$c > 0$$P \ne NP$

Wie wäre es mit Philip Maymin

" Märkte sind dann und nur dann effizient, wenn P = NP " heißt?

$P$$NP$$FP$$FNP$$P$ $=$ $NP$$P$$NP$$1$$FP$$FNP$$FNP$$FP$ $=$ $FNP$$P$ $=$ $NP$