Was für ein mathematischer Hintergrund wird für die Komplexitätstheorie benötigt?

79

Ich bin derzeit ein Student im Grundstudium, der in diesem Jahr seinen Abschluss machen muss. Nach dem Abschluss überlege ich, auf einen TCS-Master / PhD hinzuarbeiten. Ich habe mich gefragt, welche Bereiche der Mathematik für das TCS hilfreich sind, insbesondere die (klassische) Komplexitätstheorie.

Welche Bereiche halten Sie für unerlässlich, wenn Sie Komplexitätstheorie studieren möchten? Kennen Sie gute Lehrbücher, die diese Bereiche abdecken? Falls ja, geben Sie bitte deren Schwierigkeitsgrad an (Einsteiger, Absolventen usw.).

Wenn Sie ein Feld in Betracht ziehen, das in der Komplexitätstheorie nicht häufig verwendet wird, es aber für TCS als kritisch erachtet, verweisen Sie bitte auch darauf.

Chazisop
quelle
14
Ich empfehle Ihnen, einen Standardtext zur Komplexitätstheorie wie Arora / Barak oder Papadimitriou zu lesen. Wenn Sie nicht weiterkommen, weil Sie die Mathematik nicht verstehen, versuchen Sie, die zugehörige Mathematik im Detail zu lernen, bevor Sie fortfahren.
Robin Kothari
8
Nachdem Sie getan haben, was Robin vorgeschlagen hat, beginnen Sie, an einigen kleinen offenen Problemen zu arbeiten. Sie werden sich angeregt fühlen, die Mathematik zu lernen, die dahinter steckt. Als Student finde ich es nicht sehr effizient, ein mathematisches Fach nur zum Lernen zu erlernen.
Alessandro Cosentino

Antworten:

53

Wenn Sie sich die Antworten auf diese TCS StackExchange-Frage ansehen , werden Sie feststellen , dass in der Komplexitätstheorie so gut wie jeder Bereich der Mathematik von Bedeutung sein kann. Wenn Sie sich also wirklich für ein Gebiet der Mathematik interessieren, das nicht verwandt zu sein scheint, sollten Sie es trotzdem studieren. Wenn es jemals für die Komplexitätstheorie relevant wird, gehören Sie zu den wenigen Komplexitätstheoretikern, die es verstehen.

Peter Shor
quelle
20
Diese Antwort bedeutet nicht, dass Sie die Felder, von denen wir wissen, dass sie zusammenhängen, nicht untersuchen sollten (siehe die anderen Antworten). Ich würde sagen, dass diese lineare Algebra, Graphentheorie, Wahrscheinlichkeitstheorie, grundlegende abstrakte Algebra und grundlegende Logik umfassen.
Peter Shor
6
Natürlich, wenn Sie so etwas wie einen Beitrag zu Mulmuleys Programm zum Nachweis von P NP leisten wollen, brauchen Sie viel, viel, viel mehr Mathematik als dies.
Peter Shor
34

Sie sollten das Buch von Dexter Kozen über die Theorie der Berechnung zu Ihrer Liste hinzufügen . Deckt die Grundlagen der Komplexitätstheorie sehr effektiv ab, und das kurze Vortragsformat ist großartig.

In Bezug auf den mathematischen Hintergrund zusätzlich zu dem, was oben erwähnt wurde:

  • Wahrscheinlichkeitstheorie
  • Lineare Algebra und abstrakte Algebra
  • Graphentheorie
  • Grundlogik

Ich glaube nicht, dass Sie ein Meister dieser Themen sein müssen, aber es ist auf jeden Fall hilfreich, ein bestimmtes Komfortniveau zu haben.

Suresh Venkat
quelle
32

A C 0 Das Buch Extremal Combinatorics von Stasys Jukna ist IMO in der Komplexitätsgemeinschaft zu wenig bekannt. Es ist eine großartige Sammlung kombinatorischer Techniken, die hauptsächlich mit Blick auf ihre Anwendungen in TCS (meistens Komplexität) geschrieben wurden. Eine Reihe wichtiger Komplexitätstechniken werden in ihrem kombinatorischen Kontext erörtert, darunter berühmte Ergebnisse wie Monotone- und Schaltkreisuntergrenzen, aber auch einige sehr schöne Ergebnisse, die Sie sonst vielleicht nicht finden. Und es gibt viele Übungen.AC0

Meines Wissens nach ist es das einzige veröffentlichte Buch, das sich eingehend mit der linearen Algebra in der Kombinatorik befasst. Es gibt einen Entwurf eines Manuskripts von Babai und Frankl, der viel ausführlicher ist, der jedoch weder veröffentlicht noch online ist:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

Wie Sie wahrscheinlich wissen, ist die probabilistische Methode in der Kombinatorik in der Komplexitätstheorie sehr wichtig, sogar zentral. Das Buch von Jukna befasst sich damit, wird aber (mit vielen anderen schönen Beispielen) von Alons und Spencers berühmtem Buch The Probabilistic Method ausführlicher behandelt .

Andy Drucker
quelle
2
In diesem Sinne möchte ich auf die wunderschön geschriebene Anleitung zur Entropiemethode "Entropy and Counting" von Jaikumar Radhakrishnan hinweisen. Die Entropiemethode ist ein weiteres Werkzeug, das sich sehr gut anwenden lässt, wenn sich die richtige Gelegenheit ergibt.
Arnab
27

In den vorherigen Antworten wurden bereits die grundlegenden Antworten aufgeführt: Wahrscheinlichkeitstheorie, Kombinatorik, lineare Algebra, abstrakte Algebra (endliche Felder, Gruppentheorie usw.).

Ich würde hinzufügen:

Fourier-Analyse , siehe z. B. Ryan O'Donnels Kurs: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Codierungstheorie , siehe Madhu Sudans Kurs: http://people.csail.mit.edu/madhu/coding/course.html

Informationstheorie , das Standardbuch ist Elemente der Informationstheorie: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

Es gibt auch Darstellungstheorie, zufällige Spaziergänge und vieles mehr, was ich wahrscheinlich vergessen habe ...

Dana Moshkovitz
quelle
5
Die meisten Dinge, die Sie gerade lernen, je nachdem, wohin
Ihre
22

Abgesehen von grundlegenden Dingen, wahrscheinlich:

  • Kombinatorik - Sie können feststellen, dass Sie Dinge ziemlich regelmäßig zählen
  • Stochastik - Für durchschnittliche Fallanalysen und randomisierte Algorithmen

Ich mag die Konkrete Mathematik von Knuth. Es gibt einen guten Überblick / Grundkenntnisse über viele wichtige Werkzeuge.

Wenn Sie gerne Funktionen (siehe Generierungsfunktionalität von Wilf) als Werkzeug generieren , ist auch eine komplexe Analyse hilfreich.

Raphael
quelle
Ich liebe Konkrete Mathematik, aber es ist ein bisschen esoterisch. Ich würde zuerst ein Mainstream-Buch wie Camerons "Combinatorics" empfehlen.
Emil
7
Hier ist mein Eindruck - Concrete Math scheint ein großartiges Buch zu sein, um zu lernen, wie man Algorithmen genau (oder fast genau) analysiert, Knuths Stärke. Wenn Sie das möchten, rocken Sie weiter. Beachten Sie jedoch, dass in den meisten Abhandlungen zur Komplexitätstheorie viel weniger genaue Grenzen festgelegt sind, sodass die Techniken der CM weniger relevant sind.
Andy Drucker
1
Einige könnten sagen, das liegt daran, dass Komplexitätstheoretiker faule Penner sind. Aber ich denke, es liegt daran, dass (a) genaue Grenzen mehr Aufwand bedeuten als es sich lohnt, (b) oft eine so große Lücke zwischen bekannten oberen und unteren Grenzen besteht, dass kleine Verfeinerungen auf beiden Seiten von geringem Wert sein können.
Andy Drucker
Ich sollte sagen, es sind alle möglichen coolen Sachen in dem Buch - meine Bemerkungen betreffen hauptsächlich das Material über exakte Lösungen von Summationen und Wiederholungsrelationen.
Andy Drucker
22

Sanjeev Arora hat ein schönes Dokument für einen Abschlusskurs (für Studenten im ersten Studienjahr) namens "Theoretiker-Toolkit", das viele grundlegende Informationen enthält, die ein Theoriestudent kennen sollte. Viele dieser Dinge können Sie warten, bis Sie die Schule abgeschlossen haben, aber Sie erhalten eine gute Vorstellung davon, was Sie wissen müssen, und einige der Voraussetzungen.

Lev Reyzin
quelle
20

Ein weit verbreitetes, wenn auch keineswegs universelles Paradigma für viele erfolgreiche Forscher in der TCS-Community ist das folgende: Kennen Sie einige Grundlagen auf Bachelor-Niveau, wie Logik, lineare Algebra, Wahrscheinlichkeit, Optimierung, Graphentheorie, Kombinatorik und grundlegende abstrakte Algebra. Überdies zwingen Sie sich nicht, etwas anderes zu lernen, bis Sie wirklich glauben, dass Sie es brauchen, um das Problem zu lösen, mit dem Sie seit Monaten zu kämpfen haben, oder wenn Sie glauben, dass Sie wirklich gerne etwas dazu lernen würden.

"Woher weiß ich, dass ich es brauche, wenn ich es noch nie gesehen habe?", Fragst du? Gute Frage. Manchmal hat man Glück und spürt es: "Weißt du was, dieses Unterproblem, das ich anzupacken versuche, klingt sehr nach der Fourier-Transformation, über die Fred nicht die Klappe hält. Ich muss das überprüfen oder Fred fangen in einem Raum und lassen Sie ihn mich kurz durch die Grundlagen führen. " Ein anderes Mal fängst du ein paar kenntnisreichere Leute als dich in einem Raum ein, indem du ein Seminarvortrag hältst oder so, und jammerst darüber, wie du dieses Problem nicht lösen kannst, bis Fred mit "Hey, ich wette, dass du das bist kann dies mit der Fourier-Analyse lösen. Lassen Sie mich Ihnen zeigen, wie. " Am Ende bekommst du eine gemeinsame Arbeit mit Fred, du hast etwas Neues gelernt und du und Fred sind jetzt die besten Freunde und gehen jeden zweiten Samstagabend trinken.

TCSgradstudent
quelle
18

Ich denke, eine Liste von Bereichen der Mathematik, die nicht nützlich sind, wäre viel kürzer als eine Liste von Bereichen, die es gibt! Mir fällt nichts ein.

Lerne, was auch immer für dich interessant ist und / oder wie es im Moment aussieht. Auch wenn Sie es nicht direkt verwenden, wird es Ihnen helfen, andere Dinge zu lernen, die Sie tun.

Jeffε
quelle
4
Ich werde diese Antwort unterstützen. Welche Mathematik Sie am interessantesten finden, führt Sie zu den interessantesten Problemen und zu den Problemen, für deren Lösung Sie sich gut eignen.
Derrick Stolee
12

Ich empfehle, sich diese Bücher anzuschauen:

Außerdem können Sie anhand von Themen der MFCS- Konferenz (Mathematical Foundations of Computer Science) erfahren, welche Art von Hintergrund Sie benötigen. (Vorsichtsmaßnahme: Die Konferenz enthält hochentwickelte Themen. Sie müssen diese nicht beherrschen. Versuchen Sie einfach, den Überblick zu behalten.)

MS Dousti
quelle
9

Die Zahlentheorie wurde nicht erwähnt, ist jedoch ein sehr wichtiges Werkzeug für viele kryptografische und komplexitätstheoretische Konstruktionen.

Arnab
quelle
6

Die Darstellungstheorie endlicher Gruppen (auch über endliche Felder) kann für verschiedene Aufgaben überraschend nützlich sein, darunter:

  • Matrixmultiplikationsalgorithmen ( Cohn - Kleinberg-Szegedy-Umans )

  • lokal dekodierbare Codes konstruieren (siehe zB dieses Paper von Klim Efremenko)

  • Anwendungen im Quantencomputing (Hidden Subgroup Problem für Nicht-Label-Gruppen, multiplikative Gegner-Methode)

Sn

Marcin Kotowski
quelle
Vergessen Sie nicht, deterministische Konstruktionen von Expander-Graphen
Sasho Nikolov
Sie meinen algebraische Konstruktionen mit der Eigenschaft (T) a la Lubotzky? In diesem Fall hat dies einen etwas anderen Geschmack als die obigen Beispiele (verwenden Sie keine Irreps mit endlichen Gruppen).
Marcin Kotowski
4

Ich empfehle das Buch von Garey und Johnson zu lesen

Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit .

Dies kann mit sehr wenig mathematischem Hintergrund gelesen werden. Ich denke, dieses Buch ist eine Freude zu lesen, und ich würde es als erstes Buch über Papadimitriou und Arora / Barak empfehlen. Sobald Sie dies gelesen haben, können Sie in die anderen Bücher eintauchen und verschiedene Teile der Mathematik identifizieren, die Sie benötigen, um die fortgeschrittenen Themen zu verstehen, an denen Sie interessiert sind.

Emil
quelle
1
Ich habe Komplexität aus diesem Buch gelernt, finde es aber unausgewogen, mit vielen fummeligen, aber letztendlich unwichtigen Details, aber es enthält keine Informationen zu Themen, die selbst zum Zeitpunkt der Erstellung des Buches wichtig waren. Andererseits ist es gelegentlich ein wichtiges Nachschlagewerk. Im Gegensatz dazu ist Kozens in einer anderen Antwort erwähnter Text klar, umfassend und modern.
András Salamon
1

Es war einmal der Grundkurs CS464 (2002) bei UWaterloo CS, in dem Christos H. Papadimitrious Computational Complexity , Addison-Wesley, 1994, verwendet wurde.

Die aufgeführten Hintergrundthemen umfassen Turing-Maschinen, Unentscheidbarkeit, Zeitkomplexität und NP-Vollständigkeit.

Durchsuchen Sie für Hintergrundinformationen Ihre Bibliothek in der Nähe von QA267.G57 (Goddards Introducing the Theory of Computation , basierend auf ein oder zwei schnellen Lesevorgängen und deren Verfügbarkeit für mich) Theorie von der reinen mathematischen Seite wäre auch nützlich.)

josh0
quelle
2
Ich wünschte, ich hätte genug Ruf, um abzustimmen. Warum diese Verweise auf eine Universität und ihre Bibliothek?
Alessandro Cosentino
2
FWIW, QA267.G57 ist eine Rufnummer der Library of Congress, die ein weit verbreiteter Bibliotheksstandard ist. Es ist nicht spezifisch für die Universität von Waterloo (außer möglicherweise für die letzten Ziffern).
Emil Jeřábek