Élimination gaussienne en termes d'action de groupe

13

L'élimination gaussienne rend le déterminant d'une matrice polynomiale temps calculable. La réduction de la complexité dans le calcul du déterminant, qui est autrement la somme de termes exponentiels, est due à la présence de signes négatifs alternatifs (dont le manque rend le calcul permanent est c'est-à-dire plus difficile que problèmes ). Cela conduit à une sorte de symétrie dans le déterminant, par exemple l'échange d'une paire de lignes ou de colonnes inverse simplement les signes. J'ai lu quelque part, probablement en relation avec les algorithmes holographiques introduits par Valiant, que l'élimination gaussienne pouvait être expliquée en termes d'action de groupe et cela à son tour conduit à des techniques génériques de réduction de la complexité.N P - C#P-hardNP-C

De plus, je pense que presque toutes les sources de réduction de la complexité pour tout problème de calcul sont une sorte de symétrie présente. Est-ce vrai? Pouvons-nous formaliser rigoureusement cela en termes de théorie des groupes?

Éditer

J'ai trouvé la référence . (p. 2, dernière ligne du deuxième paragraphe). Je n'ai pas bien compris le document, si ma question est basée sur une mauvaise compréhension du document, veuillez me corriger.

DurgaDatta
la source
3
Mon point de vue personnel sur le deuxième paragraphe: Les problèmes d'intérêt général ont souvent une symétrie, qu'ils aient ou non des algorithmes efficaces. Mais à part cela, je ne vois pas la vérité dans votre sentiment que «presque toute la source de réduction de la complexité pour tout problème de calcul est une sorte de symétrie présente». Par exemple, je ne vois pas quelle symétrie l'algorithme de Kruskal utilise. De plus, l'idée que des algorithmes efficaces naissent de la symétrie des problèmes ne semble pas expliquer pourquoi la symétrie du permanent n'aide apparemment pas à le calculer efficacement.
Tsuyoshi Ito
4
Non, la symétrie ne réduit pas toujours la complexité. Chaque question intéressante sur les groupes est indécidable. Le tri ne l'est pas.
Jeffε
2
la déclaration formelle la plus proche dans cette direction qui me vient à l'esprit est la conjecture de dichotomie algébrique, qui (pour le dire très vaguement) déclare qu'un CSP est en P si et seulement s'il existe des moyens non triviaux de combiner deux solutions en une troisième solution véritablement différente . un exemple est la résolution d'un système linéaire mod 2, qui est résoluble par élimination gaussienne, et où deux solutions différentes déterminent un sous-espace affine de solutions
Sasho Nikolov
2
ah donc ce dont vous parlez en fait est GCT, qui part de l'idée que le problème permanent vs déterminant peut être compris en termes (à peu près) les symétries sous lesquelles les deux fonctions sont invariantes.
Sasho Nikolov
2
Il existe de nombreuses raisons pour lesquelles un problème admet un algorithme efficace. Convexité, sous-modularité, etc. Les symétries provoquent une explosion de cas dans certains problèmes combinatoires et sont parfois considérées comme une source d'inefficacité.
Vijay D

Réponses:

12

Dans le cas du déterminant, l'élimination gaussienne peut en effet être considérée comme équivalente à l'idée que le déterminant a un grand groupe de symétrie (d'une forme particulière) et se caractérise par ce groupe de symétrie (c'est-à-dire tout autre polynôme homogène de degré dans les variables avec ces symétries doivent être un multiple scalaire du déterminant). (Et, quant au point de @Tsuyoshi Ito selon lequel les symétries du permanent ne semblent pas aider à le calculer efficacement: bien que le permanent soit également caractérisé par ses symétries, son groupe de symétrie est beaucoup plus petit que celui du déterminant.)n 2nn2

Vous pouvez trouver une description de ceci - où les symétries du déterminant sont utilisées pour faire une élimination gaussienne, tout en prouvant que le déterminant est caractérisé par ses symétries - dans la proposition 3.4.3 de ma thèse (self plug sans vergogne - mais aussi, je ne l'ai jamais vu formulé de cette façon auparavant et écrit en détail, comme le demandait le PO, bien que je sois sûr que cela a été fait; je serais heureux si quelqu'un avait d'autres références).

En ce qui concerne l'idée que la symétrie conduit toujours à une réduction de complexité (ou non), en plus des choses déjà dans les commentaires, voir cette question et ses réponses.

Un point intéressant est que dans les premiers articles de Valiant sur ce qui est maintenant connu comme la version de Valiant de la théorie de la complexité algébrique, il essayait de faire valoir qu'une des raisons pour lesquelles le déterminant est important sur le plan du calcul est parce qu'en gros tous les algorithmes efficaces (alors) connus pourraient être réduite à l'algèbre linéaire et de là au calcul du déterminant, par exemple l'algorithme FKT pour compter les correspondances dans les graphes planaires. Il s'agit bien sûr d'une exagération, mais cela continue d'être confirmé par la recherche d'algorithmes holographiques, qui se réduisent souvent à calculer le Pfaffien (un proche parent du déterminant). Certes, Valiant savait que c'était une exagération, mais voici la citation exacte juste pour m'assurer que je ne me trompe pas ( L. Valiant. Classes d'exhaustivité en algèbre. ACM STOC 1979 ):

Nos principales conclusions peuvent être résumées comme suit:

(a) L'algèbre linéaire offre essentiellement la seule technique rapide pour calculer des polynômes multivariés de degré modéré

b) ...

Joshua Grochow
la source
7

Il existe des cas où les symétries d'un problème (semblent) caractériser sa complexité. Un exemple très intéressant est celui des problèmes de satisfaction des contraintes (CSP).

Définition de CSP

UΓkUk{0,1}VΓϕ:VU

ΓU{0,1}ΓkU{0,1}

Polymorphismes

ϕ1,,ϕtF:UtUϕϕ(v)=F(ϕ1(v),,ϕt(v))Ft

F(X,y,z)=X+y+z(mod2)fF(X,X,y)=F(y,X,X)=yF

En revanche, les disjonctions de 3 littéraux n'ont que des dictateurs comme polymorphismes, c'est-à-dire des fonctions de type .F(X,y)=X

Polymorphismes et complexité (la conjecture de dichotomie)

Les polymorphismes ont en fait des implications informatiques: si un CSP admet tous les polymorphismes de , alors est polynomial-time réductible à . C'est une façon de dire formellement qu'un CSP qui est "moins symétrique" qu'un autre CSP est en fait plus difficile.Γ 2 Γ 1 Γ 2 Γ 2 Γ 1Γ1Γ2Γ1Γ2Γ2Γ1

Un problème ouvert majeur dans la théorie de la complexité est de caractériser la dureté des CSP. La conjecture de dichotomie de Feder et Vardi indique que tout CSP est soit en P soit en NP-complet. La conjecture peut être réduite à un énoncé sur les polymorphismes: un CSP est NP-dur si et seulement si les seuls polymorphismes qu'il admet sont des "dictateurs" (sinon c'est en P). C'est-à-dire qu'un CSP n'est difficile que s'il n'existe aucun moyen local de former de véritables nouvelles solutions à partir d'anciennes solutions. La partie if (dureté) est connue, mais la seule partie if (conception d'un algorithme de polytime) est ouverte.

Cependant, un cas important où nous avons une dichotomie est celui des CSP booléens (où ). Selon le théorème de Schaefer , un CSP booléen est en P s'il admet l'un des 6 polymorphismes, sinon il est NP-complet. Les six polymorphismes sont fondamentalement ce dont vous avez besoin pour résoudre le problème soit par élimination gaussienne ou par propagation (comme vous le faites avec le horn-sat par exemple), ou pour le résoudre par une affectation triviale.U={0,1}

Pour en savoir plus sur les polymorphismes, l'algèbre universelle et la conjecture de dichotomie, vous pouvez consulter l' enquête de Bulatov .

Polymorphismes et approximabilité

Je recommande également une conférence IAS par Prasad Raghavendra où il met son résultatdonnant une approximation optimale de tout CSP en supposant la conjecture de jeux unique dans un cadre similaire. À un niveau élevé, si tous les polymorphismes (cela doit être généralisé pour gérer les problèmes d'approximation) d'un CSP sont proches des dictateurs, on peut utiliser le CSP pour concevoir un moyen de tester si une fonction est un dictateur, et cela se révèle être soyez tout ce dont vous avez besoin afin de réduire la dureté de l'approximation des jeux uniques. Cela donne la direction de dureté de son résultat; la direction algorithmique est que lorsqu'un CSP a un polymorphisme qui est loin d'être un dictateur, on peut utiliser un principe d'invariance (généralisation des théorèmes des limites centrales) pour argumenter qu'un algorithme d'arrondi SDP donne une bonne approximation. Une intuition vraiment sommaire pour la partie algorithmique: un polymorphisme qui est loin d'être un dictateur t se soucier s'il est donné comme arguments (une distribution sur) les affectations de variables ou des variables aléatoires gaussiennes qui approchent localement une distribution sur les affectations de variables. C'est de la même manière qu'une fonction de somme "ne se soucie pas" si on lui donne des variables aléatoires discrètes avec une petite variance ou des valeurs gaussiennes avec la même variance, par le théorème central limite. Les variables aléatoires gaussiennes dont nous avons besoin peuvent être calculées à partir d'une relaxation SDP du problème CSP. On retrouve donc un polymorphisme loin d'un dictateur, on lui donne les échantillons gaussiens, et on récupère une bonne solution. si on lui donne des variables aléatoires discrètes avec une petite variance ou des RV gaussiens avec la même variance, par le théorème de la limite centrale. Les variables aléatoires gaussiennes dont nous avons besoin peuvent être calculées à partir d'une relaxation SDP du problème CSP. On retrouve donc un polymorphisme loin d'un dictateur, on lui donne les échantillons gaussiens, et on récupère une bonne solution. si on lui donne des variables aléatoires discrètes avec une petite variance ou des RV gaussiens avec la même variance, par le théorème de la limite centrale. Les variables aléatoires gaussiennes dont nous avons besoin peuvent être calculées à partir d'une relaxation SDP du problème CSP. On retrouve donc un polymorphisme loin d'un dictateur, on lui donne les échantillons gaussiens, et on récupère une bonne solution.

Sasho Nikolov
la source
2
Bulatov a également prononcé un discours invité sur son enquête lors de la RSE 2011.
Tyson Williams