Il y a quelques années, Joel Friedman avait écrit un article reliant les limites inférieures du circuit à la cohomologie de Grothendieck (voir articles: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Cette ligne de pensée a-t-elle apporté de nouvelles informations sur la complexité booléenne, ou reste-t-il plutôt une curiosité mathématique?
cc.complexity-theory
lower-bounds
circuit-complexity
boolean-functions
Marcin Kotowski
la source
la source
Réponses:
J'ai correspondu avec Joel Friedman il y a environ 3 ans sur ce sujet. À l'époque, il avait déclaré que son approche n'avait pas permis de mieux comprendre la théorie de la complexité, même s'il pensait toujours que c'était une solution prometteuse.
Au fond, Friedman tente de reformuler les problèmes de complexité des circuits dans le langage des gerbes sur une topologie de Grothendieck. On espère que ce processus permettra d'appliquer l'intuition géométrique au problème de la recherche de limites inférieures de circuit. Bien que cela vaille la peine de vérifier si ce chemin mène quelque part, il existe des raisons heuristiques d'être sceptique. L'intuition géométrique fonctionne mieux dans le contexte de variétés lisses, ou de choses suffisamment similaires pour que les variétés lisses ne soient pas totalement dégradées. En d'autres termes, vous avez besoin d'une certaine structure pour permettre à l'intuition géométrique de prendre pied. Mais les limites du circuit, de par leur nature même, doivent faire face des calculs arbitraires, qui sont difficiles à analyser précisément parce qu’ils semblent sans structure. Friedman admet d'emblée que les topologies de Grothendieck qu'il considère hautement combinatoires et très éloignées des objets d'étude habituels en géométrie algébrique.
En guise de commentaire, je dirais qu'il est important de ne pas être trop enthousiasmé par une idée simplement parce qu'elle utilise des machines inconnues et très puissantes. Le mécanisme peut être très efficace pour résoudre les problèmes pour lesquels il a été conçu, mais pour qu’il soit utile pour attaquer un problème difficile connu dans un autre domaine, il doit exister un argument convaincant sur la raison pour laquelle le mécanisme étranger est bien adapté pour traiter les problèmes fondamentaux. obstacle au problème de l'intérêt.
la source
Je pense que Timothy Chow a tout à fait raison. J'ai ma propre liste d'idées personnelles concernant des variétés "lisses", ou des concepts tels que le comptage de composants connectés ou de monômes associés aux derniers échelons inférieurs de "l'échelle de la cohomologie" - tous se sont avérés non comme des prédicats de dureté ( variations sur) la construction de Mayr-Meyer montrant EXPSPACE-complétude de divers problèmes liés à GCT. Mon dernier commentaire sur son dernier paragraphe est que je pense qu’il faut une sorte de machinerie puissante…!
la source