Cet article traite de la complexité computationnelle du problème de marginalisation, c'est-à-dire du calcul de la somme de toutes les affectations à une entrée d'une fonction. Bien que ce problème soit généralement complexe, il existe des classes de fonctions pour lesquelles la marginalisation est facile à calculer, telles que les fonctions qui calculent des polynômes multivariables exprimables dans des circuits arithmétiques de taille polynomiale (par exemple, des modèles probabilistes). Cet article répond négativement à la question de savoir si toutes les fonctions dotées d'un algorithme de marginalisation en temps polynomial peuvent être exprimées de manière concise dans de tels circuits. En supposant $\textsf{FP}\neq \textsf{P}$ (ce qui implique $\textsf{P} \neq \textsf{NP}$), nous montrons qu'il existe des fonctions simples dont la marginalisation est traçable, mais qui ne peuvent être efficacement représentées dans un modèle connu. À cette fin, nous présentons une hiérarchie de classes de complexité correspondant à des formes fortes de marginalisation, dont le calcul est efficace dans un modèle de circuit connu. Enfin, nous présentons des résultats de complétude montrant que lorsqu'il existe une RAM réelle efficace qui effectue une marginalisation de preuve virtuelle de la fonction, il existe un circuit compact pour la représentation polynomiale multivariable de cette fonction.
