Quelqu'un peut-il fournir une explication concise de l'approche GCT de Mulmuley compréhensible par les non-experts? Une explication qui conviendrait pour une page Wikipedia sur le sujet (qui est stub pour le moment). Motivation: Je suis en train de "co-lire" l'ouvrage de Scott Aaronson sur...
On prétend parfois que la théorie de la complexité géométrique de Ketan Mulmuley est le seul programme plausible pour régler les questions en suspens de la théorie de la complexité, comme la question P vs NP. Plusieurs théoriciens de la complexité connus ont commenté positivement le programme....
Il semble que la théorie de la complexité géométrique nécessite une connaissance approfondie des mathématiques pures telles que la géométrie algébrique, la théorie de la représentation. Bien que je sois un étudiant en informatique et que je n’ai PAS de cours de mathématiques très abstraites et...
Autant que je sache, le programme de théorie de la complexité géométrique tente de séparer en prouvant que le permament d'une matrice à valeurs complexes est beaucoup plus difficile à calculer que le déterminant.VP≠VNPVP≠VNPVP \neq VNP Après avoir parcouru les documents du GCT, la question que je...
Dans ce billet d'invité de Josh Grochow sur le blog de complexité, il rend compte d'un récent atelier consacré au GCT qui s'est tenu à Princeton en juillet. Plusieurs des participants ont fait valoir que nous devrions utiliser GCT pour attaquer des problèmes plus faciles que vs N P afin de...
Récemment, Ryan Willams a prouvé que la constructivité dans la preuve naturelle est inévitable pour dériver une séparation des classes de complexité: et . T C 0N E X PNEXP\mathsf{NEXP}T C0TC0\mathsf{TC}^{0} La constructivité dans la preuve naturelle est une condition que toutes les preuves...
La formulation exacte du titre est due à Anand Kulkarni (qui a proposé la création de ce site). Cette question a été posée à titre d'exemple, mais je suis incroyablement curieux. Je connais très peu de choses sur la géométrie algébrique, et en fait, je n'ai aussi qu'une compréhension superficielle...
Je me demandais quels papiers je devrais lire pour comprendre cette question Une connexion inattendue à d'autres domaines des mathématiques tels que la géométrie algébrique ou la cohomologie supérieure. Peut-être même un domaine des mathématiques pas encore développé. Peut-être que quelqu'un...
La complexité des circuits en profondeur bornée est l'un des principaux domaines de recherche de la théorie de la complexité des circuits. Cette rubrique a des origines dans des résultats comme "la fonction de parité n'est pas dans " et "la fonction mod n'est pas calculée par ", où est la classe...
Ma question concerne les théorèmes 4.1 et 4.2 dans "Théorie de la complexité géométrique V" . Le premier théorème indique qu'il existe un algorithme EXPSPACE pour construire hsop pour (voir les définitions dans l'article) sur C (en fait sur un champ arbitrairement fermé algébriquement de...