Este artículo aborda la complejidad computacional del problema de marginalización, es decir, el cálculo de la suma de todas las asignaciones a alguna entrada de una función. Si bien generalmente es computacionalmente difícil, existen clases de funciones para las cuales la marginalización es fácil de calcular, como las funciones que calculan polinomios multivariables que pueden expresarse en circuitos aritméticos de tamaño polinomial (p. ej., modelos probabilísticos). Este artículo presenta una respuesta negativa a la pregunta de si todas las funciones que tienen un algoritmo de marginalización en tiempo polinomial pueden expresarse concisamente en dichos circuitos. Suponiendo $\textsf{FP}\neq \textsf{P}$ (lo que implica $\textsf{P} \neq \textsf{NP}$), demostramos que existen funciones simples con marginalización trazable, pero que no pueden representarse eficientemente en un modelo conocido. Para ello, presentamos una jerarquía de clases de complejidad correspondientes a formas fuertes de marginalización, que se ha demostrado que se calculan eficientemente en un modelo de circuito conocido. Finalmente, presentamos resultados de completitud que muestran que cuando existe una RAM real eficiente que realiza una marginalización de prueba virtual de la función, existe un circuito compacto para la representación polinomial multivariable de esa función.
