Des algorithmes surprenants pour compter les problèmes

54

Certains problèmes de comptage impliquent de compter de manière exponentielle beaucoup de choses (par rapport à la taille de l'entrée), tout en ayant d'étonnants algorithmes déterministes exacts à temps polynomial. Les exemples comprennent:

Une étape clé dans ces deux exemples consiste à réduire le problème de comptage au calcul du déterminant d’une matrice donnée. Un déterminant est lui-même, bien sûr, une somme exponentielle de nombreuses choses, mais peut étonnamment être calculé en temps polynomial.

Ma question est la suivante: existe-t-il des algorithmes exacts et déterministes «étonnamment efficaces», connus pour compter des problèmes qui ne se réduisent pas à calculer un déterminant?

Ashley Montanaro
la source
8
BTW, beaucoup plus de problèmes de comptage se réduisent à calculer le déterminant. Le déterminant entier est complet pour la classe GapL, qui contient #L.
5501

Réponses:

11

Je ne sais pas si les problèmes suivants réduisent ou non le calcul du déterminant, mais je vais quand même énumérer:

v0vfvfv0

2) Compter le nombre de solutions de problèmes définissables dans la logique MSO dans des structures de largeur d'arbre délimitée. Voir par exemple le papier qui porte sur les œuvres de Courcelle, Arnborg et autres .

f:{0,1}n{0,1}xf(x)=1Uf|x|0|x|f(x)|1UfHn|0|0

Mateus de Oliveira Oliveira
la source
Merci - les articles (2) et (3) sont intéressants mais ne correspondent pas du tout à ce que je cherchais; Compter les problèmes avec la largeur d'arbre délimitée semble plus comme des cas particuliers où la structure avec laquelle vous travaillez est en réalité polynomiale. J'étais plus intéressé dans les cas où il y a "vraiment" de manière exponentielle beaucoup d'objets à compter, mais ils peuvent d'une manière ou d'une autre être comptés comme par magie en temps polynomial.
Ashley Montanaro
Cela ne signifie-t-il pas que, si vous utilisez un codage unaire, l'algorithme a besoin de temps exponentiel pour écrire le nombre? Est-il possible que ce problème soit résolu en utilisant l’encodage binaire, mais cela me semble tout à fait intuitif.
Antonio Valerio Miceli-Barone
2
@ Miceli-Barone, ce que vous dites s’appliquerait à n’importe quel algorithme poly-temps produisant un nombre. Le déterminant lui-même serait plutôt grand dans le pire des cas dans le unaire
Raphaël,
(n+1)n+122n
11

Dans le cadre de Holant, il y a plusieurs cas qui sont des raisons traitables (pour des raisons non triviales) autres que via des matchgates dans des graphes plans.

1) les portes de Fibonacci

2) N'importe quel jeu de signatures affines .

3) #SPC pondérés non négatifs

... pour en nommer quelques-uns.

En outre, le théorème BEST fournit un algorithme polynomial pour compter le nombre de circuits eulériens dans un graphe dirigé, bien qu'une partie de l'algorithme utilise un calcul déterminant.

Tyson Williams
la source