Programme GCT de Mulmuley

38

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. Selon Mulmuley, il faudra beaucoup de temps pour atteindre les résultats souhaités. Entrer dans cette zone n’est pas une tâche facile pour les théoriciens de la complexité générale et nécessite des efforts considérables pour maîtriser la géométrie algébrique et la théorie de la représentation.

  1. Pourquoi GCT est-il considéré comme capable de régler P vs NP? Quelle est la valeur de la demande si on attend plus de 100 ans pour y parvenir? Quels sont ses avantages par rapport aux autres approches actuelles et à celles susceptibles d’augmenter au cours des 100 prochaines années?

  2. Quel est l'état actuel du programme?

  3. Quel est le prochain objectif du programme?

  4. Y a-t-il eu des critiques fondamentales du programme?

Je préférerais des réponses qui soient compréhensibles par un théoricien de la complexité général avec le minimum de connaissances acquises en géométrie algébrique et en théorie de la représentation.

Anonyme
la source
12
Avez-vous vu le tutoriel de Mulmuley à FOCS (disponible à techtalks.tv/talks/1301 ) et avez-vous lu l'exposition de Ken Regan: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley a clairement donné son intuition sur la raison pour laquelle il pense que son programme est viable (et je pense qu'il soutient que c'est même dans une certaine mesure nécessaire), et aussi pourquoi c'est difficile.
Sasho Nikolov
5
Articles de blog connexes: 1 , 2 . Aussi Scott écrit: « Le programme GCT de Mulmuley est la seule approche de P vs NP j'ai vu que même a des aspirations sérieuses à « savoir sur » beaucoup de techniques triviaux pour résoudre les problèmes en P (au moins, la correspondance et la programmation linéaire) Pour moi, c’est probablement l’argument le plus puissant en faveur de GCT. "
Kaveh
7
Je pense que GCT vise VP vs VNP et non P vs NP.
Iddo Tzameret
6
@Iddo: En réalité, il peut viser beaucoup de choses (plus que ce à quoi il est destiné actuellement). Par "perm v det sur " , on vise à ¯ V P w s vs V N P (voir arxiv.org/abs/0907.2850 ). Cependant, sur des corps finis et pour des fonctions autres que perm et det, il peut être dirigé directement vers P vs NP. CVPws¯VNP
Joshua Grochow
4
@Mohammad: Ce n'est pas parce qu'une solution serait inattendue et nécessiterait des idées entièrement nouvelles que la solution ne sera pas utilisée. En effet, beaucoup pensent déjà que la résolution de P vs NP par n'importe quelle méthode nécessitera des idées entièrement nouvelles ...
Joshua Grochow

Réponses:

23

Comme l'ont souligné de nombreuses autres personnes, Mulmuley, Regan et d'autres ont déjà beaucoup parlé de ces questions. Je n’offrirai ici qu’un bref résumé de ce que je pense être des points clés qui n’ont pas encore été mentionnés dans les commentaires.

  1. En ce qui concerne la raison pour laquelle GCT est considéré comme vraisemblablement capable de montrer nombreuses réponses ont déjà été données ailleurs et dans les commentaires ci-dessus, bien que personne ne nous ait encore dit qu'il semble éviter les barrières connues (relativisation, algébrization, preuves naturelles). ) En ce qui concerne sa valeur - je pense que même si cela nous prend 100 ans, nous apprendrons quelque chose de nouveau sur la complexité en chemin en l’étudiant sous cet angle.PNP

    • Certains progrès ont été accomplis dans la compréhension des variétés algébriques, des représentations et des questions algorithmiques soulevées dans les GCT. Les principaux chercheurs à ma connaissance qui ont travaillé sur ce sujet sont (sans ordre particulier): P. Burgisser, C. Ikenmeyer, M. Christandl, JM Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar et, bien entendu, K. Mulmuley et M. Sohoni.

    • n2+232n2+O(n)

    • N. Kayal a rédigé quelques articles sur la question algorithmique du test lorsqu'un polynôme est dans l'orbite d'un autre ou en est une projection. Il montre que ces problèmes sont généralement difficiles à résoudre, mais que, pour des fonctions spéciales telles que les polynômes symétriques permanents, déterminants et élémentaires, ces problèmes sont décidables en P. Ceci est un pas en avant vers certaines conjectures de Mulmuley fermeture - sont en P pour des fonctions spéciales telles que déterminant).

  2. Je n'ai pas beaucoup plus spécifique à dire à ce sujet que la réponse à 2.

  3. Autant que je sache, il n'y a pas eu de critique fondamentale , en ce sens que je n'ai vu aucune critique qui discrédite réellement le programme. Il y a certes eu des discussions sur les raisons pour lesquelles de telles techniques devraient être nécessaires, la valeur du programme compte tenu des horizons à long terme escomptés, etc., mais je dirais qu'elles sont plus saines que les critiques fondamentales.

Joshua Grochow
la source
1
@ user124864: En principe, oui. GCT est simplement une approche permettant d'afficher les limites inférieures, quelles qu'elles soient. Il semble que cela devrait fonctionner mieux pour les fonctions caractérisées par leurs symétries, mais cette dernière propriété ne dépend pas de la valeur numérique de la limite inférieure que vous voulez afficher (par exemple, quasipoly vs exp).
Joshua Grochow