Mathematische Implikationen komplexitätstheoretischer Vermutungen außerhalb des TCS

25

Kennen Sie interessante Konsequenzen von (Standard-) Vermutungen in der Komplexitätstheorie in anderen Bereichen der Mathematik (dh außerhalb der theoretischen Informatik)?

Ich würde Antworten vorziehen, wo:

  • Die Vermutung der Komplexitätstheorie ist so allgemein und normal wie möglich. Ich bin auch mit den Konsequenzen der Härte spezifischer Probleme einverstanden, aber es wäre schön, wenn die Probleme allgemein als schwierig eingestuft würden (oder zumindest in mehr als ein paar Artikeln untersucht wurden).

  • die Implikation ist eine Aussage, von der nicht unbedingt bekannt ist, dass sie wahr ist, oder andere bekannte Beweise sind erheblich schwieriger

  • je überraschender die Verbindung, desto besser; Insbesondere sollte die Implikation keine explizite Aussage über Algorithmen sein

"Wenn Schweine fliegen könnten, würden Pferde singen" Verbindungen sind auch in Ordnung, solange die fliegenden Schweine aus der Komplexitätstheorie stammen und die singenden Pferde aus einem mathematischen Gebiet außerhalb der Informatik.

Diese Frage ist in gewissem Sinne "das Gegenteil" einer Frage, die wir über überraschende Verwendungen der Mathematik in der Informatik hatten. Dick Lipton hatte einen Blog-Post genau in dieser Richtung: Er schreibt über die Konsequenzen der Vermutung, dass Factoring eine große Schaltkreiskomplexität hat. Die Konsequenzen sind, dass bestimmte diophantische Gleichungen keine Lösungen haben, eine Art Aussage, die sich nur sehr schwer bedingungslos beweisen lässt. Der Beitrag basiert auf der Arbeit mit Dan Boneh, aber ich kann keine Zeitung finden.

EDIT: Wie Josh Grochow in den Kommentaren bemerkt, ist seine Frage nach der Anwendung von TCS auf die klassische Mathematik eng verwandt. Meine Frage ist einerseits freizügiger, weil ich nicht auf der Einschränkung "klassischer Mathematik" bestehe. Ich denke, der wichtigere Unterschied ist, dass ich auf einer nachgewiesenen Implikation von einer Komplexitätsvermutung zu einer Aussage in einem mathematischen Bereich außerhalb des TCS bestehe. Die meisten Antworten auf Joshs Frage sind nicht von diesem Typ, sondern geben Techniken und Konzepte wieder, die in der klassischen Mathematik nützlich sind und von TCS entwickelt oder inspiriert wurden. Trotzdem ist mindestens eine Antwort auf Joshs Frage eine perfekte Antwort auf meine Frage: Michael Freedmans ArtikelDies ist durch eine mit meiner identische Frage motiviert und beweist einen Satz in der Knotentheorie, der von abhängig ist P#PNP. Er argumentiert, dass der Satz außerhalb der Reichweite der gegenwärtigen Techniken in der Knotentheorie zu liegen scheint. Nach dem Theorem von Toda kollabiert die Polynomhierarchie, wenn P#P=NP , so dass die Annahme durchaus plausibel ist. Ich bin an ähnlichen Ergebnissen interessiert.

Sasho Nikolov
quelle
Verwandte: Implikationen, nicht für Mathematik, sondern für "physikalische Realität"
Austin Buchanan
Ist das dasselbe wie cstheory.stackexchange.com/questions/149/… ? Oder soll diese Frage breiter sein als diese?
Joshua Grochow
3
@ Joshua, es gibt einige Überschneidungen, aber ich denke, sie sind unvergleichlich. Einerseits bestehe ich nicht stark auf "klassischer" Mathematik, dh Nichtkomplexitätsergebnisse in der Quantenmechanik sind in Ordnung. Andererseits möchte ich direkte Implikationen von CC-Vermutungen auf mathematische Theoreme außerhalb von TCS haben, während sich viele der Antworten auf Ihre Frage auf Techniken beziehen , die in TCS entwickelt wurden und für die klassische Mathematik von Nutzen sind. Dennoch ist cstheory.stackexchange.com/a/163/4896 eine perfekte Antwort auf meine Frage. Zu viel Überlappung?
Sasho Nikolov
1
Ich hätte vielleicht meine Antwort auf Joshs Frage hier posten sollen : Bürgissers Konjektur impliziert Ergebnisse auf elliptischen KurvenL .
Bruno
1
@Sasho: Ich denke es ist okay. Danke fürs klarstellen. (Übrigens, als ich bei meiner anderen Frage "klassisch" sagte, wollte ich die Quantenmechanik nicht ausschließen - tatsächlich sind die Quantenfeldtheorie und die Quantenalgebra heutzutage beide wichtige mathematische Themen, die in einer großen Anzahl von (sogar führenden) mathematischen Abteilungen studiert wurden .)
Joshua Grochow

Antworten:

14

Hier ist ein weiteres Beispiel aus der Graphentheorie. Der Graph-Minor-Satz besagt, dass es für jede Klasse ungerichteter Graphen, die unter Minderjährigen geschlossen ist, eine endliche Obstruktionsmenge O b s ( G ) gibt, so dass ein Graph genau dann in G ist, wenn er keinen Graphen enthält in O b s ( G ) als Moll. Der Graph-Minor-Satz ist jedoch von Natur aus nicht konstruktiv und sagt nichts darüber aus, wie groß diese Hindernissätze sind, dh wie viele Graphen er für eine bestimmte Wahl von G enthält .GObs(G)GObs(G)G

In Too Many Minor Order Obstructions hat Michael J. Dinneen gezeigt, dass unter einer plausiblen komplexitätstheoretischen Vermutung gezeigt werden kann, dass mehrere solcher Hindernissätze groß sind. Man betrachte zum Beispiel die parametrisierte Klasse von Gattungsgraphen mit höchstens k . Wenn k zunimmt, können wir erwarten, dass die Hindernissätze O b s ( G k ) immer komplizierter werden, aber wie viel? Dinneen zeigte, dass, wenn die Polynomhierarchie nicht auf ihre dritte Ebene zusammenbricht, es kein Polynom p gibt, so dass die Anzahl der Hindernisse in O b s (GkkkObs(Gk)pist begrenzt durchp(kObs(Gk) . Da die Anzahl der geringfügigen Hindernisse für die Gattung Null (dh planar) nur zwei beträgt ( O b s ( G 0 ) = { K 5 , K 3 , 3 } ), ist dieses superpolynomiale Wachstum nicht sofort offensichtlich (obwohl ich es glaube) kann bedingungslos nachgewiesen werden). Das Schöne an Dinneens Ergebnis ist, dass es sich auf die Größen von Hindernissätzen bezieht, dieeinemparametrisierten Satz von Nebenidealen G k entsprechen, für die das kleinste k bestimmt wirdp(k)Obs(G0)={K5,K3,3}Gkkfür die NP-hart ist; in allen solchen parametrisierten Nebenidealen müssen die Größen der Hindernissätze superpolynomiell wachsen. GGk

Bart Jansen
quelle
Danke Bart! Das ist sehr interessant. Ich akzeptiere Ihre Antwort als die am höchsten bewertete. Vielen Dank an alle für die Antworten!
Sasho Nikolov
6

Hier ein Beispiel: Die Komplexität der Berechnungen und die Informationsasymmetrie in Finanzprodukten von Arora, Barak und Ge zeigen, dass es rechnerisch schwierig sein kann, Derivate korrekt zu bewerten (dh NP-hart) - sie verwenden den dichtesten Teilgraphen als eingebettetes hartes Problem.

In die gleiche Richtung und viel früher ist die berühmte Zeitung von Bartholdi, Tovey und Trick über die Härte der Wahlmanipulation.

Suresh Venkat
quelle
2
Klar, bis zu einem gewissen Grad sind dies immer noch Komplexitätsergebnisse (mit sozialen Implikationen). Ich dachte an Ergebnisse, bei denen es nicht um Algorithmen geht. Trotzdem sind beide großartig!
Sasho Nikolov
Ich war mir nicht ganz sicher, wonach du suchst. Ich vermute, Sie wollen so etwas wie die Umkehrung von "Quanten- und Klassik-Kollaps geschlossener zeitlicher Kurven"?
Suresh Venkat
1
Tatsächlich ist das CTC-Ergebnis ein perfektes Beispiel. Ich meine nicht einmal das Umgekehrte, sondern die Aussage selbst im Gegensatz: Wenn Quanten und Klassik nicht zusammenbrechen, gibt es keine (polynomiellen) CTCs.
Sasho Nikolov
1
Du sagst also, ich sollte eine neue Antwort posten :)?
Suresh Venkat
Ich glaube, ich sage das :)
Sasho Nikolov
6

Wie von Sasho vorgeschlagen, lautet meine Antwort auf die Frage " Anwendungen von TCS auf die klassische Mathematik? ":

Lτ

L

¹ Die Hypothese besagt, dass, wenn ein Polynom p ein konstantfreies Geradenprogramm (oder eine arithmetische Schaltung) der Größe τ hat , seine Anzahl von ganzzahligen Wurzeln höchstens ( 1 + τ ) beträgt.τpτ(1+τ)cc

Bruno
quelle
5

S2kS2k2δk

Es ist sehr im Geiste von Mike Freedmans Artikel, der zuvor erwähnt wurde.

Izaak Meckler
quelle
-6

Es scheint, dass viele TCS-Komplexitätsklassen-Trennungsfragen wichtige Auswirkungen auf die Mathematik haben. Insbesondere die P = & Dgr; NP-Frage scheint in vielen Bereichen sehr tiefe Verbindungen zu haben, und dazu gehört auch die Mathematik. Einige bemerkenswerte Fälle in diesem Bereich:

  • Es hat sich gezeigt, dass das zu Beginn des 20. Jahrhunderts formulierte Hilberts- Nullstellensatz-Problem eine enge Beziehung zur Komplexität von P vs. NP aufweist, z . Dies ist ein fortlaufendes Forschungsgebiet, z. B. in Computeralgebra, Kombinatorik und Komplexität: Hilberts Nullstellensatz und NP-vollständige Probleme von Margulies.

  • Fagins Theorem (Wikipedia):

    Fagins Theorem ist ein Ergebnis der deskriptiven Komplexitätstheorie, die besagt, dass die Menge aller Eigenschaften, die in der existentiellen Logik zweiter Ordnung ausgedrückt werden können, genau die Komplexitätsklasse NP ist. Es ist bemerkenswert, da es sich um eine Charakterisierung der Klasse NP handelt, die kein Rechenmodell wie eine Turing-Maschine aufruft.

    Die hauptsächliche / überraschende Implikation von P = NP würde hier bedeuten, dass alle logischen Aussagen zweiter Ordnung effizient berechnet werden könnten.

  • Ein anderer Fall ist, dass es verschiedene NP-vollständige Probleme gibt, die größtenteils nur in mathematischen Begriffen angegeben werden (z. B. keine Bezugnahme auf TCS-Konzepte wie TMs, Nichtdeterminismus usw.). Diese Liste könnte sehr umfangreich sein, wenn die Graphentheorie (vernünftigerweise) als mathematisch angesehen wird. Aber auch enge Interpretationen von "mathematisch" führen zu Fällen, zum Beispiel in der Zahlentheorie.

    a,b,cxcx2a(modb)

vzn
quelle
3
Sie haben die Frage nicht verstanden: Alle Ergebnisse, die Sie erwähnen, beziehen sich auf Komplexität. Ich möchte eine nicht-Komplexität Folge einer Aussage in der Komplexitätstheorie
Sasho Nikolov