Por encima de #P y contando problemas de búsqueda

Estaba leyendo el artículo de Wikipedia sobre el problema de las ocho reinas. Se afirma que no existe una fórmula conocida para el número exacto de soluciones. Después de buscar un poco, encontré un artículo llamado "Sobre la dureza de contar problemas de mapeos completos". En este documento hay un problema, que se muestra como mucho más difícil que #queens, que está más allá de #P. Al echar un vistazo a los números de #queens contados exhaustivamente en el artículo de Wikipedia, parecen ser súper exponenciales.

Quiero preguntar si hay un nombre para esta clase o si en general hay problemas de conteo que pertenecen a las clases por encima de #P (con la decisión no en PSPACE, por supuesto, porque sería obvio).

Finalmente, quiero preguntar si hay otros resultados conocidos para otros problemas de búsqueda, como encontrar un punto de tres colores en el Lemma de Sperner, por ejemplo (PPAD completo).

Si la función f está en #P, entonces, dada una cadena de entrada x de cierta longitud N, el valor f (x) es un número no negativo limitado por . (Esto se deduce de la definición, en términos de número de rutas de aceptación de un verificador NP).$2^{poly(N)}$

Esto significa que muchas funciones f se encuentran fuera de #P por razones poco interesantes, ya sea porque f es negativa o, en el caso que mencione, porque la función crece más rápido que . Pero para el problema de n -queens como se modela en el artículo, esto es solo un artefacto de la decisión de los autores de permitir que el valor de entrada n se codifique en binario. Si la entrada esperada era la cadena unaria 1 n , entonces f ( 1 n ) : = (número de n válido$2^{poly(N)}$$n$$n$$1^n$$f(1^n) :=$$n$-queen configuraciones) sin duda estaría en #P, por un simple verificador NP que verifica la validez de una configuración dada.

Si desea explorar algunas funciones que (conjeturalmente) se encuentran fuera de #P por razones más interesantes, considere, por ejemplo, estas:

• UNSAT: si ψ es una fórmula booleana insatisfactoria, de lo contrario f ( ψ ) : = 0 . Esta función no está en #P, a menos que NP = coNP. Probablemente tampoco esté en la clase de conteo más general GapP; es decir, UNSAT probablemente no sea la diferencia f - g de dos funciones #P. Sin embargo, se encuentra en la clase de complejidad de conteo más general P # P , que de hecho contiene toda la Jerarquía polinómica según el teorema de Toda.$f(\psi) := 1$$\psi$$f(\psi) := 0$$P^{\# P}$

Es posible que no le guste ese ejemplo porque no es un "problema de conteo" natural. Pero los siguientes dos serán:

• $f(\psi(x, y)) :=$$x$$\psi(x, \cdot)$$y$

• $f(\psi(x, y)) :=$$x$$y$$\psi(x, y) = 1$

No se sabe que los dos últimos problemas sean computables de manera eficiente incluso con acceso Oracle a #P. Sin embargo, son computables dentro de la llamada "jerarquía de conteo". Para algunos problemas más naturales clasificados dentro de esta clase, consulte, por ejemplo, este artículo reciente.

El conteo de equilibrios de Nash es aparentemente # P-difícil, ver aquí . Además, incluso los problemas en los que el problema de búsqueda es fácil puede ser #P difícil de contar, por ejemplo, contando coincidencias perfectas.

$\#PSPACE$$\#EXPTIME$

La complejidad de los modelos de conteo de la lógica temporal de tiempo lineal por Hazem Torfah, Martin Zimmermann