Comments on Un problème d'algorithmique (en lien secret avec la formule de Weyl)

B. (2018-07-18T07:51:02Z)

Si tu es intéressé par calculer les polynômes S, Δ et X, tu peux regarder du côté de la complexité algébrique (<URL: https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity >). Dans ce cadre, il existe des circuits de taille polynomiale pour le déterminant et de taille O(2^n n²) pour le permanent. Ce qui signifie que les polynômes S et Δ peuvent être petitement représentés, mais pas forcément sous forme de liste de monômes. Ensuite, si tu sais que le nombre de monôme total est petit, il est possible de les développer efficacement en utilisant les algorithmes d'interpolation creuse (bcp de papiers là dessus, une bonne référence est dans la thèse de Dan Roche : <URL: https://www.usna.edu/Users/cs/roche/research/phd/ch7-interp.pdf >). Enfin, pour le polynôme X, si tu sais que c'est un polynôme qui est le quotient de deux déterminants, tu peux aussi le calculer efficacement : <URL: http://perso.ens-lyon.fr/pascal.koiran/Publis/issac08.pdf >.

Olivier Bailleux (2018-07-16T22:35:28Z)

Oui, le problème AS semble très coriace, à part si la contrainte de sommes nulles des coordonnées des vecteurs change drastiquement la donne.

Le problème de décision que j'évoquais, appelons-le ASdec, *sans* les contraintes de sommes nulles, me semble être NP-complet, par réduction depuis l'équation pseudo-Booléenne a1 z1 + … + an zn = K (ai et K entiers, zi = 0 ou 1) vers ASdec avec x = (a1,…,an,0,…,0) et y = (1,…,1,0,..,.0).

C'est effectivement un peu hors sujet :-). Je n'ai pas de piste évidente si on ajoute les contraintes de sommes nulles.

@Vicnent: Je ne pense pas que réduire ce problème à SAT apporterait grand chose. Si le but est de montrer qu'il est NP-complet, il faudrait faire la réduction inverse, mais partir de l'égalité pseudo-Booléenne sus-mentionnée, dont la satisfaisabilité est un problème NP-complet, me parait plus direct, sous réserve bien sûr d'une erreur de ma part.

Ruxor (2018-07-16T14:20:54Z)

@Olivier Bailleux, @vicnent: En plus de mon commentaire précédent, je devrais préciser que je ne cherche pas forcément un algorithme polynomial, juste un algorithme « significativement moins pourri » que l'algorithme naïf en n! (et donc, en fait, je crois que j'ai répondu à ma question en reconnaissant un permanent, parce que <URL: http://en.wikipedia.org/wiki/Computing_the_permanent > m'apprend que le permanent se calcule avec un algorithme en O(2^n·n²) opérations arithmétiques, ce qui doit devenir O(2^n·n³) à cause des degrés de mes polynômes, mais c'est effectivement mieux que O(n!·n) ; après, il faut vérifier qu'il n'y a pas une arnaque dans l'histoire). Mais la question de si l'approche consistant à calculer Χ(x,y) comme rapport de déterminants pour en déduire l'ensemble des exposants fonctionne bien est intéressante.

vicnent (2018-07-16T12:18:09Z)

@ Olivier Bailleux (2018-07-16T12:59:20+0200)

je me disais la même chose. faudrait se pencher sur le problème mais cette histoire de n! d'une part et le fait qu'une permutation ne donne pas à priori d'information sur le valeur de la permutation suivante n'augure rien de bon. Faudrait donc regarder comment le modéliser comme un pb pour lequel on pourrait le réduire à SAT, classiquement…

Ruxor (2018-07-16T12:05:01Z)

Je viens de me rendre compte que mon Δ(x,y) est précisément le déterminant de la matrice dont les coefficients sont les t^{x_i·y_j}, et que S(x,y) est son permanent. (J'ai ajouté un paragraphe à ce sujet.) Du coup, ça résout mon problème (AA) et ça suggère fortement que (AS) n'est Pas Sympa.

@jonas:

Your remark about n=1 reminds me of a number of times when I attended a lecture where Jean-Pierre Serre was in the audience. The lecturer would make a statement and Serre would burst out saying "this is completely wrong! this is not possible!", at which point the lecturer would start panicking and ask themselves whether the great Serre had already found a counterexample to their theorem: and then Serre would point out that the statement obviously did not work for n=0 and that the lecturer had forgotten to state the hypothesis "n>0". I suspect that Serre does this on purpose to force mathematicians to be more careful about their statements and not carelessly exclude trivial cases (he told me that it is one of his pet peeves). He's right, of course, and so are you. In this particular case, the statement that the Δ(x,y) polynomial vanishes at t=1 is still true for n=1 for an even more trivial reason (x and y are both zero so Δ(x,y)=t); it is wrong, however, for n=0. I made the appropriate corrections.

Re posting on Stackexchange: indeed, that is what I do, but I try to force myself to think a fairly long time about my questions before I post them there. Here the problem is that I have a little too much to say, so I need to organize my thoughts first, hence the blog post. Since writing it helped me realize the determinant/permanent connection (first paragraph of this comment), I now see things in a different light.

@Olivier Bailleux: Je suis vraiment une quiche en algorithmique. 😖

Maintenant que j'ai fait la connexion avec le déterminant (premier paragraphe de ce commentaire), il est possible que ça fournisse un algorithme efficace pour calculer Χ(x,y), et comme il me semble que l'ensemble des exposants du polynôme en question est le même que celui de S(x,y), ça montrerait que ce dernier se calcule efficacement. Mais de nouveau, je n'ai pas les idées bien claires sur la complexité effective de tout ça.

Olivier Bailleux (2018-07-16T10:59:20Z)

Considérons un problème de décision associé : soient x, y les deux vecteurs et a un entier. Est-ce que a apparaît au moins une fois dans les valeurs des produits scalaires possibles ?

Ce problème est dans NP. Est-il NP-complet ?

jonas (2018-07-16T10:58:44Z)

> Régulièrement je tombe sur des problèmes mathématiques qui me paraissent tellement simples, tellement naturels et/ou tellement évidents (je veux dire évidents à poser, pas forcément évidents à résoudre !) que c'est inconcevable qu'il n'existe pas déjà une littérature abondante à leur sujet.

Yes, that's normal. You already know what to do: post on MathOverflow or Theoretical Computer Science SE.

> [About problem (AA)] Cette fois, le polynôme prend la valeur 0 en t=1 (il y a autant de permutations impaires que de permutations paires).

If 1 < n. Be careful.


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: b532f0


Recent comments