Quel type d'arrière-plan mathématique est nécessaire pour la théorie de la complexité?

Je suis actuellement un étudiant de premier cycle, obligé d'obtenir un diplôme cette année. Après avoir obtenu mon diplôme, j’envisage d’obtenir un master / doctorat en sciences de la technologie. J'ai commencé à me demander quels domaines des mathématiques sont considérés comme utiles pour le SDC, en particulier la théorie de la complexité (classique).

Quels domaines considérez-vous comme essentiels pour quelqu'un qui veut étudier la théorie de la complexité? Connaissez-vous de bons manuels couvrant ces domaines et, dans l’affirmative, veuillez indiquer leur niveau de difficulté (débutant, diplômé, etc.).

Si vous considérez un domaine qui n'est pas fortement utilisé dans la théorie de la complexité mais que vous considérez comme critique pour le SDC, veuillez également le renvoyer.

Si vous examinez les réponses à cette question de TCS StackExchange , vous verrez qu'il est possible que pratiquement tous les domaines des mathématiques jouent un rôle important dans la théorie de la complexité. Donc, si vous êtes vraiment intéressé par un domaine des mathématiques qui ne semble pas être lié, allez-y et étudiez-le quand même. Si cela devient un jour pertinent pour la théorie de la complexité, vous serez l’un des rares théoriciens de la complexité à la comprendre.

Vous devriez ajouter le livre de Dexter Kozen sur la théorie du calcul à votre liste. Couvre très efficacement les bases de la théorie de la complexité, et le format de conférence courte est excellent.

En termes de fond mathématique, en plus de ce qui est mentionné ci-dessus:

• Théorie des probabilités
• Algèbre linéaire et algèbre abstraite
• la théorie des graphes
• logique de base

Je ne pense pas que vous ayez besoin de maîtriser ces sujets pour commencer, mais il est certainement utile d’avoir un certain niveau de confort.

A C $\bullet$ Le livre Extremal Combinatorics , de Stasys Jukna, est trop peu connu de l’OMI au sein de la communauté de la complexité. C'est un grand ensemble de techniques combinatoires écrites en grande partie en vue de leurs applications dans le TCS (principalement la complexité). Un certain nombre de techniques de complexité importantes sont discutées dans leur contexte de combinatoire, y compris des résultats célèbres tels que des limites inférieures de circuits monotones et , mais également des résultats très intéressants que vous ne pourriez pas rencontrer autrement. Et il y a beaucoup d'exercices.$AC^0$

C'est (à ma connaissance) le seul livre publié qui traite en profondeur de la méthode de l'algèbre linéaire en combinatoire - un outil simple et puissant à connaître. Il y a un projet de manuscrit de Babai et Frankl qui va beaucoup plus en profondeur, mais ce n'est pas publié ni en ligne:

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

$\bullet$ Comme vous le savez probablement, la méthode probabiliste en combinatoire est très importante, voire centrale, dans la théorie de la complexité. Le livre de Jukna le couvre, mais il est traité plus en profondeur (avec beaucoup d'autres beaux exemples) par le célèbre livre de Alon and Spencer, The Probabilistic Method.

Les réponses précédentes indiquaient déjà les bases: théorie des probabilités, combinatoire, algèbre linéaire, algèbre abstraite (champs finis, théorie des groupes, etc.).

J'ajouterais:

Analyse de Fourier , voir par exemple le cours de Ryan O'Donnel: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Théorie du codage , voir le cours de Madhu Sudan: http://people.csail.mit.edu/madhu/coding/course.html

Théorie de l’information , le livre type est Elements of Information Theory: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

Il y a aussi la théorie de la représentation, des marches aléatoires et bien d'autres que j'oublie probablement ...

En dehors des choses de base, probablement:

• Combinatoire - Vous pourriez vous retrouver à compter les choses assez régulièrement
• Stochastics - Pour les analyses de cas moyennes et les algorithmes aléatoires

J'aime les mathématiques concrètes de Knuth. Il donne une bonne vue d'ensemble / connaissance de base de nombreux outils importants.

Si vous aimez générer des fonctions (voir generationfunctionology de Wilf) en tant qu’outil, une analyse complexe est également utile.

Sanjeev Arora a un beau document pour un cours de troisième cycle (pour les étudiants de 1ère année) qu'il a enseigné appelé "boîte à outils du théoricien", qui contient beaucoup de matériel de base qu'un étudiant en théorie devrait connaître. Vous pouvez attendre de nombreuses études supérieures pour apprendre beaucoup de ces choses, mais cela vous donnera une bonne idée de ce que vous devez savoir et de certaines conditions préalables.

Un paradigme commun, mais certainement pas universel, pour de nombreux chercheurs performants de la communauté TCS est le suivant: Connaître quelques notions de base au niveau du premier cycle, telles que la logique, l’algèbre linéaire, les probabilités, l’optimisation, la théorie des graphes, la combinatoire, l’algèbre abstraite de base. Au-delà de cela, ne vous forcez pas à apprendre autre chose avant de penser que vous en avez réellement besoin pour résoudre le problème avec lequel vous vous débattez depuis des mois ou si vous pensez que vous aimeriez vraiment apprendre quelque chose pour le plaisir de le faire.

"Comment puis-je savoir que j'en ai besoin si je ne l'ai jamais vu auparavant?", Demandez-vous? Bonne question. Parfois, vous avez de la chance et vous le sentez: "Vous savez quoi, ce sous-problème que je tente de résoudre ressemble beaucoup à ce truc de transformation de fourier, Fred ne se taira pas. Je vais devoir vérifier ou piéger Fred dans une pièce et faites-le me donner un aperçu rapide des bases. " D’autres fois, vous emprisonnez dans une pièce un groupe de personnes plus avisées que vous, disons en prononçant un discours dans un séminaire ou quelque chose du genre, et en gémissant sur le fait que vous ne pouvez pas résoudre ce problème avant que Fred ne sonne avec "Hey, je vous parie que vous peut résoudre cela avec l'analyse de Fourier. Laissez-moi vous montrer comment. " En fin de compte, vous obtenez un document commun avec Fred, vous avez appris quelque chose de nouveau et Fred et vous êtes maintenant vos meilleurs amis et sortez boire un verre tous les samedis soirs.

Je pense qu'une liste de champs de mathématiques qui ne sont pas utiles serait beaucoup plus courte qu'une liste de champs! Je ne peux pas penser à aucun.

Étudiez tout ce qui vous semble intéressant en mathématiques et / ou ce dont vous avez besoin pour le moment. Même si vous ne l'utilisez pas directement, cela vous aidera à apprendre d'autres choses que vous faites.

La connaissance de la logique mathématique de base est, à mon avis, un atout. Vous pouvez consulter les deux livres de Cori et Lascar.

Logique mathématique: un cours avec exercices, première partie

Logique mathématique: un cours avec des exercices, partie II

Je recommande de jeter un oeil à ces livres:

• Le compagnon de Princeton aux mathématiques
• La logique en informatique; Modélisation et raisonnement sur les systèmes

De plus, les sujets de la conférence MFCS (Fondements mathématiques en informatique) peuvent vous indiquer le type de formation dont vous pourriez avoir besoin. (Mise en garde: la conférence comprend des sujets très avancés. Vous n'avez pas besoin de les maîtriser. Essayez simplement d'avoir une vue d'ensemble.)

La théorie des nombres n'a pas été mentionnée, mais c'est un outil très important pour de nombreuses constructions cryptographiques et théoriques de la complexité.

La théorie de la représentation des groupes finis (également sur des corps finis) peut être étonnamment utile pour diverses tâches, notamment:

• algorithmes de multiplication matricielle ( Cohn - Kleinberg-Szegedy-Umans )

• construire des codes décodables localement (voir par exemple cet article de Klim Efremenko)

• applications en informatique quantique (problème de sous-groupe caché pour les groupes non-labeliens, méthode de l'adversaire multiplicatif)

Bien que, pour être honnête, la théorie de la représentation au niveau requis ci-dessus puisse être apprise en deux soirées (peut-être trois si vous voulez apprendre la théorie de la représentation du groupe symétrique ), vous ne devriez donc pas être obligé de l'apprendre à l'avance.$S_n$

Je recommande de lire le livre de Garey et Johnson

Computers and Intractability: Guide de la théorie de la NP-complétude .

Cela peut être lu avec très peu de fond mathématique. Je pense que ce livre est un plaisir à lire, et je le recommanderais comme premier livre par rapport à Papadimitriou et Arora / Barak. Une fois que vous avez lu ceci, vous pouvez vous plonger dans les autres livres et identifier différentes mathématiques dont vous avez besoin pour comprendre les sujets avancés qui vous intéressent.

Il était une fois le cours de premier cycle CS464 (2002) à UWaterloo. CS utilisait la complexité informatique de Christos H. Papadimitriou , Addison-Wesley, 1994.

Les matières d'arrière-plan répertoriées incluent les machines de Turing, l'indécidabilité, la complexité temporelle et le caractère NP complet.

Pour vous renseigner, parcourez votre bibliothèque proche de QA267.G57 ( Introduction de Goddard à la théorie du calcul , basée sur une ou plusieurs lectures rapides et sa disponibilité, me semble couvrir le côté fond de l’arrière-plan; j’ai le sentiment que certains la théorie du côté des mathématiques pures serait également utile.)