Ergebnisse, die das Vorhandensein / Nichtvorhandensein endlicher Graphen mit bestimmten berechenbaren Eigenschaften zeigen, implizieren bestimmte Komplexitätsergebnisse

Gibt es bekannte Ergebnisse, die zeigen, dass das Vorhandensein (oder Nichtvorhandensein) endlicher Graphen mit bestimmten berechenbaren Eigenschaften bestimmte Komplexitätsergebnisse impliziert (wie P = NP)?

Hier ist ein völlig hypothetisches Ergebnis: Wenn ein endlicher Graph mit distingushed Kanten A, B, C und D existiert, so dass alle maximalen Übereinstimmungen entweder alle A, B, C und D enthalten oder keine von A, B, C und D. dann ist P = NP.

Ein Ergebnis dieser Art wurde von Lipton bewiesen "Beim Nachweis, dass ein Graph keine große Clique hat: Ein Zusammenhang mit der Ramsey-Theorie" . Er verbindet Vermutungen der unteren Schranken mit rein graphentheoretischen Ergebnissen und zeigt, dass, wenn nicht in c o N T I M E ( n O ( log n ) ) / ( log log n ) enthalten ist , die Unannäherung von M A X - C L I Q U $NP$$coNTIME(n^{O(\log n)})/(\log \log n)$$MAX-CLIQUE$impliziert, dass es Graphen mit sauberen Ramsey-theoretischen Eigenschaften gibt. (Definitionen finden Sie im Papier.) Ich habe keine Ahnung, ob Fortschritte beim Nachweis erzielt wurden, ob solche Grafiken tatsächlich existieren oder nicht.

Entschuldigung, ich bin erst jetzt auf diese 1-jährige Frage gestoßen ...

Tatsächlich gibt es viele Ergebnisse, die zeigen, dass explizite Diagramme mit einigen Eigenschaften starke Untergrenzen für Boolesche Funktionen implizieren. Angenommen, Graphen mit hoher affiner oder projektiver Dimension implizieren starke Untergrenzen für Formeln und Verzweigungsprogramme. Es gibt auch "einfachere" Messungen von Graphen, gute Untergrenzen, die große Konsequenzen für die Komplexität der Berechnungen haben würden. Lassen Sie mich einige davon skizzieren.

Zeigen Sie Diagramme als Kantengruppen an. Sei die kleinste Zahl s, so dass G als Schnittpunkt von ≤ s Graphen geschrieben werden kann, von denen jeder eine Vereinigung von ≤ s Bikliken ist (zweigeteilte vollständige Graphen). Einfache Zählung zeigt , dass s ( G ) ≥ n 1 / 2 für fast alle zweiteiligen n × n Graphen. Aber nach Valiants Ergebnissen ist jeder explizite zweigeteilte Graph G (genauer gesagt eine Folge von Graphen) mit s ( G ) $s(G)$$s$$G$$\leq s$$\leq s$$s(G)\geq n^{1/2}$$n\times n$$G$. für eine Konstante c > 0 würde ein altes Problem lösen: würde eine boolesche Funktion ergeben, die von einer logarithmischen Tiefenschaltung linearer Größe nicht berechnet werden kann. Es wird vermutet, dass dichte Graphen ohne K 2 , 2 große s ( G $s(G)\geq n^c$$c>0$$K_{2,2}$$s(G)$

Noch besser sei die kleinste Anzahl von Fanin- 2- Vereinigungs- und Schnittoperationen, die ausreichen, um G ausgehend von vollständigen Sternen zu erzeugen (Graphen vom Typ K 1 , n oder K n , ( 4 + c) ) n für eine Konstante c > 0 würde eine explizite Boolesche Funktion ergeben, die Schaltungen exponentieller Größe erfordert! Wenn der Graph die Dimension m × $Star(G)$$2$$G$$K_{1,n}$ ). Die Zählung zeigt, dass die meisten GraphenStar(G)=Ω( n 2 / logn) haben. Aber jedesGmitSt$K_{n,1}$$Star(G)=\Omega(n^2/\log n)$$G$mit m = o ( n ) hat , hätte sogar eine Untergrenze S t a r ( G ) ≥ ( 2 + c ) n die gleichen Konsequenzen. Das Beste, was wir bisher zeigen können, ist S t $Star(G)\geq (4+c)n$$c>0$$m\times n$$m=o(n)$$Star(G)\geq (2+c)n$ . $Star(G)\geq 2n-1$

Sei die kleinste Zahl t, für die es eine Teilmenge T ⊆ { 0 , 1 , … , t } und eine Folge von t Bicliques gibt, so dass ( u , v ) ∈ G ist, wenn die Anzahl der Bicliques enthält ( u , v ) gehört T . Wiederum ergibt das Zählen S y m ( G ) ≥ n $Sym(G)$$t$$T\subseteq\{0,1,\ldots,t\}$$t$$(u,v)\in G$$(u,v)$$T$$Sym(G)\geq n/2$für die meisten Grafiken. Nach den Ergebnissen von Yao, Beigel und Tarui würde jeder explizite Graph mit größer als 2 p o l y ( ln ln n ) eine boolesche Funktion außerhalb von A C C ergeben . Warnung: "kombinatorisch kompliziert" zu sein, bedeutet nicht, dass S y m ( G ) groß ist : Es gibt stark Ramsey-Graphen, für die S y m ( G ) = O ( $Sym(G)$$2^{poly(\ln\ln n)}$$ACC$$Sym(G)$ , auch wenn T = Menge ungerader Ganzzahlen.$Sym(G)=O(\log n)$$T$

Weitere Details dazu finden Sie hier .

$f:{0,1}^n\rightarrow {0,1}^n$$O(n)$$O(\log n)$Tiefe - etwas, das wir noch lange nicht beweisen können) unter der Annahme, dass bestimmte Arten von Graphen, sogenannte Superkonzentratoren, nicht existieren. (Dies war eine asymptotische Frage und nicht nur eine Grafik.) Später zeigte er jedoch, dass diese existieren (und tatsächlich andere Verwendungszwecke haben).

Die Antwort lautet mit Sicherheit "Ja", wenn wir eher über Grafikfamilien als über bestimmte Grafiken sprechen. Zum Beispiel gibt es eine Vermutung von Mihail und Vazirani, dass alle 0/1-Polytopaldiagramme entweder gute oder sehr gute Kantenexpander sind (dh dass ihre Kantenexpansion unten durch 1 / Polynom (Grad) oder 1 begrenzt ist).

Wenn dies zutrifft, gibt es effiziente randomisierte Markov-Ketten-Monte-Carlo-Approximationsalgorithmen für eine Reihe offener kombinatorischer und Zählprobleme über eine Stichprobenstrategie von Alon, Jerrum und Sinclair.

In ähnlicher Weise kann die lineare Programmierung nicht in stark polynomieller Zeit über Kantenverfolgungsalgorithmen gelöst werden, wenn es Familien von Polytopaldiagrammen gibt, deren Durchmesser in Bezug auf die Anzahl der Facetten und den Grad des Graphen schneller wächst als jedes Polynom.

Erweiterung des Kommentars von Anand Kulkarni:

Angenommen, es gibt eine deterministische Turing-Maschine M, die SAT in Polynomzeit erkennt. Dann ist die endliche Übergangsrelation von M eine Funktion. Wir kennen TMs, die SAT in Polynomzeit erkennen, aber ihre Übergangsbeziehungen sind keine Funktionen. Beachten Sie, dass die Übergangsbeziehung ein zweigeteilter gerichteter Graph mit Tupeln von (Zustand, Bandsymbol) in der einen Zweiteilung, Tupeln von (Zustand, Bandsymbol, Verschieben) in der anderen Zweiteilung und Bögen von Paaren zu Dreifachen ist.

Wenn es also einen solchen Digraphen gibt, der eine Funktion ist, dann ist P = NP.

Dies ist natürlich keine sehr natürliche Definition, da zusätzliche Maschinen erforderlich sind, um der Anforderung Bedeutung zu verleihen, dass jeder Pfad im Zustandsraum, der den akzeptierenden Zustand erreicht, eine Länge hat, die durch ein Polynom in der Eingabegröße begrenzt ist. Es ist überhaupt nicht offensichtlich, wie die Menge der endlichen Graphen, die polytime-begrenzte Turing-Maschinen darstellen, aussieht oder ob diese Graphen interessante graphentheoretische Eigenschaften haben.