Analyse mathématique et complexité informatique?

La complexité de calcul implique de grandes quantités de combinatoire et de théorie des nombres, quelques ingrédients de la stochastique et une quantité émergente d'algèbre.

Cependant, en tant qu'analyseur, je me demande s'il existe des applications de l'analyse dans ce domaine, ou peut-être des idées inspirées par l'analyse. Tout ce que je sais qui correspond un peu à cela, c'est la transformée de Fourier sur les groupes finis.

Pouvez-vous m'aider?

Flajolet et Sedgewick ont ​​publié le livre "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html . Je ne connais pas grand-chose à ce sujet, mais les gens sur le terrain utilisent des outils d'analyse complexe. Jusqu'à présent, leurs applications semblent plus sur l'analyse d'algorithmes, pas sur la complexité de calcul, pour autant que je vois.

Les algorithmes de Markov Chain Monte Carlo sont un outil utile pour trouver des algorithmes d'approximation. Certaines techniques pour montrer que ces chaînes de Markov se mélangent sont inspirées ou proviennent directement de l'analyse - par exemple, voir le chapitre sur l'estimation du volume d'un corps convexe dans le livre de Mark Jerrum sur le comptage .

Il existe des approches analytiques du lemme de Szemerédi, qui a une application mignonne aux tests de propriétés combinatoires. Le lemme de Szemerédi pour l'analyste a un algorithme aléatoire pour trouver une partition faiblement régulière d'un graphique; voir également Limites du graphique et test des paramètres .

L'analyse fonctionnelle joue un rôle de plus en plus important dans la théorie des plongements métriques. Bien qu'il soit difficile d'énumérer tous les aspects de l'interaction, le thème principal est l'utilisation de méthodes issues de l'analyse fonctionnelle pour comprendre comment les métriques s'intègrent dans des espaces normés. Ce dernier problème se pose dans le problème de coupe le plus clairsemé, qui est un problème d'optimisation de graphique important.

Pour plus d'informations, une bonne source est n'importe quoi par Assaf Naor .

Pas sur la complexité de calcul, mais intéressant néanmoins

Certaines approches de la sémantique du calcul infini sont basées sur des espaces métriques. Googler "la sémantique de l'espace métrique" apparaît en abondance. Une référence (ancienne) sur le sujet est Control Flow Semantics par de Bakker et de Vink. Certains travaux récents ont été effectués par notre propre Neel , à savoir la sémantique ultramétrique pour les programmes réactifs . Le domaine est très différent de ceux décrits ci-dessus, mais les concepts de l'analyse trouvent certainement leur place ici.

La théorie de la mesure limitée des ressources développée par Jack Lutz est un excellent domaine pour les personnes ayant une formation en analyse. Le papier d'origine

Presque partout à haute complexité non uniforme , Jack H. Lutz, Journal of Computer and System Sciences, 1992.

généraliser la notion de mesure de Lebesgue en classes de complexité, et de nombreux ouvrages suivants peuvent être trouvés sur Internet.

$\mathsf{P}$$\mathsf{NP}$$\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{ESPACE}$$\Omega(2^n/n)$$\mathsf{ESPACE}$

Les personnes qui travaillent dans différents domaines de l'informatique peuvent bénéficier de divers sous - domaines d'analyse.

Pour vous donner un exemple concret, je vais décrire mon propre cas. Je mène des recherches sur les fondements de la cryptographie. Dans ce domaine (ainsi que dans la complexité de calcul), il existe une construction appelée l' oracle aléatoire (voir aussi cette page ). Ses différentes propriétés sont parfois étudiées en exploitant des outils de la théorie de la mesure , qui est un sous-domaine d'analyse. Un tel traitement peut être trouvé dans cet article , ainsi que dans plusieurs articles qui le citent.

Vous pouvez également jeter un oeil à Bases de l'algèbre et de l'analyse pour l'informatique par Jean Gallier. C'est un livre en cours de réalisation qui vous indique les nouveautés dans le domaine.

I believe the best connection between mathematical analysis and complexity theory is in the Blum et al's real computation model. It is still an open problem to separate NP_R from P_R, where the two classes are defined in the real computation model, in which every real number is an entity, and one regular operation (+,-,*,/) takes one step.