Algoritmos sorprendentes para contar problemas

54

Hay algunos problemas de conteo que implican contar exponencialmente muchas cosas (en relación con el tamaño de la entrada) y, sin embargo, tienen sorprendentes algoritmos deterministas exactos de tiempo polinómico. Ejemplos incluyen:

Contar combinaciones perfectas en un gráfico plano (el algoritmo FKT ), que es la base de cómo funcionan los algoritmos holográficos .
Contar árboles de expansión en un gráfico (a través del teorema del árbol de matriz de Kirchhoff ).

Un paso clave en ambos ejemplos es reducir el problema del conteo a calcular el determinante de una matriz determinada. Un determinante es en sí mismo, por supuesto, una suma de muchas cosas exponencialmente, pero sorprendentemente puede calcularse en tiempo polinómico.

Mi pregunta es: ¿existen algoritmos exactos y deterministas "sorprendentemente eficientes" conocidos para contar problemas que no se reduzcan a la computación de un determinante?

cc.complexity-theory counting-complexity big-picture Ashley Montanaro
fuente

8

Por cierto, muchos más problemas de conteo se reducen a calcular el determinante. El determinante entero está completo para la clase GapL, que contiene #L.

5501

11

No sé si los siguientes problemas se reducen o no a calcular el determinante, pero enumeraré de todos modos:

$v_0$ $v_f$ $v_f$ $v_0$

2) Contar el número de soluciones de problemas definibles en lógica MSO en estructuras de ancho de árbol acotado. Véase, por ejemplo, el documento que se basa en obras de Courcelle, Arnborg y otros .

$f:\{0,1\}^{n}\rightarrow \{0,1\}$ $x$ $f(x)=1$ $U_f$ $|x\rangle|0\rangle$ $|x\rangle|f(x)\rangle$ $|1\rangle$ $U_fH^{\otimes n}|0\rangle|0\rangle$

Mateus de Oliveira Oliveira
fuente

Gracias: los elementos (2) y (3) son interesantes, pero de alguna manera no son exactamente lo que estaba buscando; Los problemas de conteo con ancho de árbol limitado parecen más bien casos especiales en los que la estructura con la que está trabajando está realmente limitada polinomialmente. Estaba más interesado en los casos en los que hay "realmente" exponencialmente muchos objetos para contar, pero de alguna manera se pueden contar mágicamente en el tiempo polinómico.

Ashley Montanaro

¿No significa eso que, si usa una codificación unaria, el algoritmo necesita tiempo exponencial solo para escribir el número? Es posible que este problema se supere mediante el uso de codificación binaria, pero esto me parece poco intuitivo.

Antonio Valerio Miceli-Barone

2

@ Miceli-Barone, lo que usted dice se aplicaría a casi cualquier algoritmo de poli tiempo que genere un número. El determinante en sí sería bastante grande en el peor de los casos en unario.

Raphael

\frac{(n + 1)^{\frac{n + 1}{2}}}{2^{n}}

$\frac{(n + 1)^{\frac{n+1}{2}}}{2^n}$

11

Contando el número de puntos de la red en un politopo racional (cuando la dimensión es constante) en tiempo polinómico , debido a Alexander Barvinok.

Yoshio Okamoto
fuente

2

¿Cuál es la técnica principal?

Suresh Venkat

2

Una breve función generadora. El siguiente artículo expositivo nos daría más ideas. arxiv.org/abs/math/0506466

Yoshio Okamoto

11

En el marco de Holant, hay varios casos que son manejables (por razones no triviales) que no sean a través de compuertas en gráficos planos.

1) Puertas de Fibonacci

2) Cualquier conjunto de firmas afines .

3) #CSP ponderados no negativos

...para nombrar unos pocos.

Además, el Teorema BEST ofrece un algoritmo de tiempo polinómico para contar el número de circuitos de Eulerian en un gráfico dirigido, aunque parte del algoritmo utiliza un cálculo determinante.

Tyson Williams
fuente

Algoritmos sorprendentes para contar problemas

Respuestas: