Anwendungen von TCS in der klassischen Mathematik?

60

Wir in TCS verwenden häufig leistungsstarke Ergebnisse und Ideen aus der klassischen Mathematik (Algebra, Topologie, Analyse, Geometrie usw.).

Was sind einige Beispiele dafür, wann es umgekehrt gegangen ist?

Hier sind einige, die ich kenne (und die auch einen Vorgeschmack auf die Art der Ergebnisse geben sollen, nach denen ich frage):

  • Würfelschäume (Guy Kindler, Ryan O'Donnell, Anup Rao und Avi Wigderson: Kugelförmige Würfel und Runden in hohen Dimensionen, FOCS 2008)
  • Das geometrische Komplexitätstheorieprogramm. (Obwohl dies technisch eine Anwendung der algebraischen Geometrie und Darstellungstheorie auf das TCS ist, wurden sie veranlasst, neue Quantengruppen und neue rein algebro-geometrische und darstellungstheoretische Ideen bei der Verfolgung von P vs NP einzuführen.)
  • Arbeiten Sie an metrischen Einbettungen, die von Approximationsalgorithmen und Unnäherungsergebnissen inspiriert sind

Insbesondere suche ich keine Anwendungen von TCS auf die Logik (Finite-Modell-Theorie, Beweis-Theorie usw.), es sei denn, sie sind besonders überraschend - die Beziehung zwischen TCS und Logik ist für die Zwecke dieser Frage zu eng und standardisiert und historisch.

Joshua Grochow
quelle
1
Dies ist etwas schwierig zu beantworten. Fällt die Kombinatorik außerhalb der klassischen Mathematik?
Arnab
2
Kombinatorik ist definitiv klassische Mathematik, aber ich denke, der gleiche Kommentar gilt für die Kombinatorik wie für die Logik. Also: Die Finite-Feld-Kakeya-Vermutung ist ein gutes Beispiel, wohingegen neue kombinatorische Entwürfe, die von PRGs motiviert sind, eher auf dem Spiel stehen.
Joshua Grochow
Sie finden gute Beispiele, wenn Sie nach Ergebnissen suchen, die beispielsweise in Annals of Math von der TCS-Community veröffentlicht wurden.
MCH

Antworten:

32

Expander wurden größtenteils in TCS entwickelt und haben tiefe Verbindungen und Anwendungen zur Mathematik.

Gil Kalai
quelle
22

Es gibt Dvirs Beweis für die endliche Feld-Kakeya-Vermutung.

Dai Le
quelle
3
Dies war auf ein Problem bei Extraktoren / Fusionen zurückzuführen (siehe die spätere Veröffentlichung von Zeev und Avi Wigderson). Weitere Verbesserungen (von Madhu Sudan, Shubhangi Saraf, Swastik Kopparty und Zeev Dvir) verwendeten mehr Ideen aus der theoretischen Informatik, insbesondere aus der Listendecodierung von Codes (der Methode der Multiplizität).
Dana Moshkovitz
1
Zwei Anmerkungen: Die von Dvir verwendete algebraische Methode ist eine der Methoden zur Lösung des klassischen Problems der Entfernungen für planare Mengen. terrytao.wordpress.com/2010/11/20/… und gilkalai.wordpress.com/2010/11/20/… .
Gil Kalai
2
Zweitens hatten Inzidenzmethoden und Ergebnisse aus der rechnerischen und diskreten Geometrie frühere Anwendungen auf das (echte) Kakeya-Problem.
Gil Kalai,
20

Ein nettes Beispiel, das ich kenne, ist Michael Freedmans Artikel mit dem Titel " Komplexitätsklassen als mathematische Axiome ", der eine Implikation von im Bereich der 3-Mannigfaltigkeitstopologie liefert.PPNP

Zeyu
quelle
20

Invarianzprinzipien wurden von der Härte der Approximation motiviert, sind aber nützliche analytische Theoreme. Das Prinzip: Eine Low-Degree-Funktion, bei der jede der Variablen einen geringen Einfluss hat, verhält sich nahezu gleich, egal ob es sich um unabhängige Zufallsvariablen oder um (entsprechende) Gaußsche Zufallsvariablen handelt. Dies ist eine Verallgemeinerung des zentralen Grenzwertsatzes; dort ist die Funktion der Durchschnitt der Variablen.

Rauschstabilität von Funktionen mit geringen Einflüssen: Invarianz und Optimalität E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), S. 295–341 (2010). FOCS '05.

Niedriggrad-Testsätze wurden von PCP-Anwendungen motiviert, sind jedoch interessante algebraische Sätze. Das Prinzip: Eine -Variatenfunktion über ein endliches Feld , die im Mittel über die Linien in in Hamming-Entfernung zu einem Polynom niedrigen Grades auf der Linie liegt , liegt in Hamming-Entfernung zu einem Polynom niedrigen Grades nahe an das ganze .F F n F nnFFnFn

Die Nähe des Hamming-Abstands zu einem Polynom niedrigen Grades in einem bestimmten Raum bedeutet, dass sich die Funktion mit einem Polynom niedrigen Grades auf einem nicht zu vernachlässigenden Teil des Raumes identifiziert.

Verbesserte Low-Degree-Tests und ihre Anwendungen . S. Arora und M. Sudan. In ACM STOC 1997.

Ein Niedriggradtest mit subkonstanter Fehlerwahrscheinlichkeit und eine PCP-Charakterisierung mit subkonstanter Fehlerwahrscheinlichkeit von NP , R. Raz, S. Safra, Verfahren des 29. STOC, 1997, S. 475-484

Dana Moshkovitz
quelle
19

Obwohl ich voreingenommen bin, ist es fair zu sagen, dass verschiedene Ideen von TCS dazu beigetragen haben, die inverse Vermutung für die Gowers-Norm voranzutreiben, siehe z. B. das Papier von Green und Tao .

Manu
quelle
7
Man kann auch sagen, dass Bestandteile des Beweises für Szemeredis Theorem durch das Hypergraphen-Regularitäts-Lemma (von Gowers, Tao, Rodl, Schacht und anderen) durch die Arbeit von Alon, Fischer, Shapira und anderen bei der Entwicklung stärkerer Versionen von beeinflusst wurden Graph Regularity Lemma zum Nachweis der Testbarkeit von Grapheneigenschaften.
Arnab
18

Gehört die Berechenbarkeitstheorie zum TCS? Wenn ja, dann ist Computability Theory and Differential Geometry von Bob Soare ein Beispiel, das Anwendungen von Ergebnissen aufzeigt, die er mit Csima erhalten hat.

Ich weiß nicht, warum der Link nicht angezeigt wird. Hier: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Aaron Sterling
quelle
2
Egal, ob Sie die Berechenbarkeit als Teil von TCS betrachten oder nicht, dies ist ein Beispiel, das mir sehr am Herzen liegt und das ich nur vergessen hatte zu erwähnen. Es ist noch cooler, weil es mit Kolmogorov Komplexität getan werden kann :).
Joshua Grochow
17

Extraktoren ist ein weiterer Ort, um zu suchen. Die Arbeit von Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 liefert unter anderem verbesserte Konstruktionen von Ramsey-Graphen (ein Problem, das in der diskreten Mathematik schon länger offen war).

Moritz
quelle
15

ϵ

Ilyaraz
quelle
13

Die Zick-Zack-Expander-Konstruktion wurde verwendet, um verschiedene interessante Beispiele für Gruppen mit bestimmten unerwarteten Eigenschaften zu konstruieren, siehe Meshulam-Wigderson , Rozenman-Shalev-Wigderson . Die Konstruktion selbst ist aus rein mathematischer Sicht sehr interessant, da sie völlig andere Werkzeuge (motiviert durch den CS-Gesichtspunkt des Umgangs mit Entropie) verwendete, um Expander als frühere Konstruktionen zu bauen. (Die vielleicht berühmteste Anwendung befindet sich jedoch in TCS- Reingolds Logspace-Algorithmus für ungerichtete Konnektivität .)

Boaz Barak
quelle
10

Lassen Sie mich noch ein paar Anwendungen erwähnen:

Der vielleicht wichtigste Beitrag von TCS zur reinen Mathematik ist die Kunst der Reduktion. Die Reduzierung der von TCS verwendeten Form in der Komplexität der Berechnungen und an anderen Stellen stellt ein mathematisches Paradigma / Werkzeug dar, das in TCS im Vergleich zu anderen Bereichen der Mathematik weiterentwickelt ist.

Der Begriff eines probabilistischen Beweises: Hier beziehe ich mich nicht auf die probabilistische Methode (die in der Mathematik verwurzelt ist, aber viele Anwendungen auf CS hat), sondern auf die Tatsache, dass eine mathematische Aussage wie die Aussage, die eine bestimmte Zahl beansprucht, eine Primzahl ist, kann einen Beweis erhalten "über jeden vernünftigen Zweifel hinaus". Es ist ein konzeptioneller Durchbruch von CS, obwohl es noch nicht viele Anwendungen in der Art und Weise gab, wie Mathematik praktiziert wird.

Gil Kalai
quelle
1
Mir war nicht bewusst, dass andere Bereiche der Mathematik die Idee von Reduktionen maßgeblich genutzt haben. Ich würde mich sehr über Hinweise oder Hinweise freuen, die Sie auf solche Werke geben können! Außerdem hatte ich den Eindruck, dass probabilistische Beweise aus reiner Kombinatorik stammen und nicht aus TCS?
Joshua Grochow
3
Ich habe in der überarbeiteten Version meiner Antwort erklärt, was ich unter "probabilistischem Beweis" verstehe. Reduktionen: Die Komplexität von Rechnern ist ein Bereich der Mathematik, der in der Informatik verwurzelt ist. Ein Merkmal dieses Bereichs ist die Verwendung von Reduzierungen, die auf konzeptioneller und technischer Ebene eine wichtige Rolle spielt. Es ist viel weiter entwickelt als ähnliche Techniken in anderen Bereichen der Mathematik. Die Kunst der Reduktion innerhalb von TCS kann daher als eine Hauptanwendung von TCS in der Mathematik angesehen werden. Ich denke, dass CS-Reduktionen Mathematiker auch in anderen Bereichen beeinflusst haben, und es wird noch mehr kommen.
Gil Kalai
Joshua, lass mich eine Analogie geben. Angenommen, jemand bezeichnet "Kalkül" als eine der größten Anwendungen der Physik in der klassischen Mathematik. Man kann auch sagen, dass der Kalkül hauptsächlich wichtig ist, um Probleme aus der Physik anzugreifen, die vorher keine "klassische Mathematik" waren. Trotzdem denke ich, dass der Kalkül der Hauptbeitrag der Physik zur Mathematik ist. In ähnlicher Weise sind Reduktionen, wie sie in der Komplexitätstheorie verwendet werden, ein wichtiger Beitrag von TCS zur Mathematik. Es beschreibt einen großen mathematischen Apparat und mathematische Ideen, die einen unabhängigen Wert haben. (Nicht so wichtig wie Kalkül.)
Gil Kalai
G
1
@JoshuaGrochow es wird nicht schwer sein, nicht-triviale Beispiele für "allgemeine Fälle von Sonderermäßigungen" zu finden. Zum Beispiel hat die Cassaza-Umfrage, die ich in meiner Antwort verlinkt habe, Tonnen von nicht-trivialen Reduzierungen zwischen Problemen, die dem Kadison-Singer-Problem entsprechen, von denen einige auf den ersten Blick sehr eingeschränkt sind. Ich verstehe, dass die arithmetische Geometrie auch voll von solchen Dingen ist, vielleicht wissen Sie mehr. Ich bin mir nicht sicher, inwieweit TCS eine Anerkennung für die Einführung dieses Ansatzes bei schwer zu lösenden Problemen beanspruchen kann.
Sasho Nikolov
9

Mosers konstruktiver Beweis für das Lovasz Local Lemma basiert auf Ideen der Informatik, liefert einen neuen Beweis für das Lovasz Local Lemma und löst ein Problem, über das sich die Leute schon seit geraumer Zeit Gedanken gemacht haben.

Peter Shor
quelle
9

Die Batson-Spielman-Srivastava- Barrierefunktionsmethode hat eine Reihe von Anwendungen für die Geometrie- und Funktionsanalyse, die in der Informatik entstanden sind, und ist eine sehr originelle Form eines möglichen Funktionsarguments, das an die Methode pessimistischer Schätzer erinnert. Darüber hinaus widerspricht es der gängigen Meinung, dass die Analyse des charakteristischen Polynoms von Zufallsmatrizen nicht möglich ist und man sich stattdessen besser mit Matrixmomenten befassen sollte.

Die Barrierefunktionsmethode wurde zuerst entwickelt, um die Existenz von (und die Konstruktion in deterministischer Polynomzeit) Sparsifiern von Graphen zu beweisen, die ihre spektralen Eigenschaften bewahren. Solche Sparsifier waren durch algorithmische Anwendungen motiviert: Im Wesentlichen kann jeder Algorithmus, der Schnitte ungefähr berechnen muss, beschleunigt werden, indem als Eingabe eine sparsifizierte Version der ursprünglichen Eingabe angegeben wird.

1n

Marcus, Srivastava und Spielman verwendeten die Barriere-Funktionsmethode für Steroide, die mit der Maschinerie der Interlacing-Polynome erweitert wurde , um eines der bekanntesten Probleme in der Funktionsanalyse, das Kadison-Singer-Problem, zu lösen . Dieses Problem ergibt sich aus grundlegenden Fragen in der mathematischen Physik, aber es geht viel weiter - es bekannt ist, dass sie äquivalent zu Dutzenden von Problemen der ganzen Mathematik. Ganz zu schweigen davon, dass viele Analysten (einschließlich Kadison und Singer) nicht einmal der Meinung waren, dass das Problem eine positive Lösung hat (die zitierte Umfrage von Cassaza et al. Spekuliert über mögliche Gegenbeispiele).

Sasho Nikolov
quelle
5

Ein Beispiel, das mir in den Sinn kommt, ist der Einbettungssatz von Higman und seine gruppentheoretischen Konsequenzen.

Higmans Einbettungssatz: Eine Gruppe G wird endlich mit einer rekursiven Darstellung erzeugt, wenn G eine Untergruppe einer endlich dargestellten Gruppe ist.

(Beachten Sie, dass der linke Teil der Äquivalenz eine rechnerische Komponente hat, während der rechte Teil eine rein gruppentheoretische Komponente ist.)

mike
quelle
1
GHGWord(G)NPG
5

Die Bedeutung von Zufälligkeit , was als "zufällige Folge" gilt und verwandte Fragen waren in Mathematik, Wahrscheinlichkeitstheorie und Statistik über Jahrhunderte wichtig. Die theoretische Informatik (und Komplexitätstheorie) bietet sehr solide tiefe und überzeugende Erkenntnisse für das Verständnis von Zufälligkeit.

Während die probabilistische Methode in der Mathematik begonnen hat, wird die Derandomisierung, die ein wichtiges mathematisches Konzept darstellt, hauptsächlich in der CS entwickelt.

Dies hängt mit Moritz 'Antwort zusammen.

Gil Kalai
quelle
5

Automatentheorie und Algebraizität

Die Automatentheorie lieferte einige interessante Ergebnisse zur Charakterisierung der Algebraizität. Ich erwähne zwei davon mit Referenzen. Es ist keineswegs erschöpfend.

Fq(t)

Fq(t)qq=pspsFq[[t]]Fq

Fq(t)Fq(t)

i=0aitiFq(t){ai}i=0p

Fq(t)

iIxiti,
IQFq(t)

iIaitiFq(t){ai}iIp

2. Transzendentale Zahlen

Automatische Sequenzen werden auch verwendet, um transzendentale Zahlen zu charakterisieren. Zum Beispiel,

b2xRx={xi}i=0b

  1. xx
  2. xbx
  3. x

Natürlich ist der erste Artikel ein sehr klassisches Ergebnis!

Verweise.

[1] Gilles Christol. Ensembles presque périodiques k-reconnaissables . In Theoretical Computer Science 9 (1), S. 141-145, 1979.

[2] Kiran S. Kedlaya. Endliche Automaten und algebraische Erweiterungen von Funktionsfeldern . Im Journal de Théorie des Nombres de Bordeaux 18 , S. 379-420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. Zur Komplexität algebraischer Zahlen I. Erweiterungen in ganzzahligen Basen . In Annals of Mathematics 165 (2), S. 547–565, 2007.

Bruno
quelle
Theorem (Adamczewski & Bugeaud [3]) kann falsch sein oder missverstanden werden
XL _At_Here_There
4

Lτ

L

τpτ(1+τ)cc

Bruno
quelle
1

IMHO TCS ist ein Zweig der Mathematik und ich würde es etwas breiter ausdrücken. Wir leben im algorithmischen Zeitalter, fast jeder erfindet Algorithmen, hauptsächlich Heuristiken, in allen menschlichen Aktivitäten neu. Aber einige dieser Algorithmen sind 1. gut; 2. enthalten (begrabene) Antworten auf tiefe mathematische Fragen; 3. Warten Sie auf eine professionelle mathematische Analyse / Verbesserung / Aufmerksamkeit. Meine persönliche Erfahrung: eine erstaunliche Kraft einer Heuristik für Physik / maschinelles Lernen, nämlich die Bethe-Approximation, als Beweismethode. Das Hauptproblem besteht darin, dass mögliche Begegnungen dieser Art hauptsächlich in der Branche stattfinden, in der sich niemand um diese nicht produktbezogenen Erkenntnisse / Enthüllungen kümmert.

leonidische gurvits
quelle