¿Cuál es la complejidad de contar el número de soluciones de un problema P-Space Complete? ¿Qué hay de las clases de mayor complejidad?

Supongo que se llamaría # P-Space, pero solo he encontrado un artículo que lo menciona vagamente. ¿Qué tal la versión de conteo de EXP-TIME-Complete, NEXP-Complete y EXP-SPACE-Complete? ¿Hay algún trabajo previo que pueda citarse con respecto a este o algún tipo de inclusión o exclusión como el Teorema de Toda?

cc.complexity-theory complexity-classes counting-complexity pspace Tayfun Pay
fuente

¡Estás haciendo muchas cosas en una pregunta!

Tsuyoshi Ito

#PSPACE es lo mismo que la clase de funciones que se pueden calcular en el espacio polinomial (FPSPACE).

Tsuyoshi Ito

@ Tsuyoshi Esto es cierto. Sin embargo, la mayoría de las preguntas formuladas, si no todas, pueden reformularse como una sola pregunta general: ¿Hay clases de conteo para clases superiores a

(como se puede notar en la definición de #

) y se aplican los resultados conocidos?

N P

$NP$

P

$P$

chazisop

@ Payfun Pay: no estoy completamente seguro de lo que quieres decir con clases deterministas como PSPACE, EXP, EXPSPACE. La noción de "número de soluciones" suele estar estrechamente vinculada al no determinismo, ya que puede preguntar sobre el número de caminos de aceptación, o cuantificadores / proyecciones existenciales. En el caso de PSPACE, por supuesto, puede usar la definición de cuantificadores alternos, pero luego debe especificar qué cuantificadores desea contar, o el hecho de que NPSPACE = PSPACE.

Joshua Grochow

Como se mencionó en varios comentarios, no está totalmente claro lo que querría significar para #PSPACE. La mejor apuesta sería tomar el análogo acolchado de #L que está bien estudiado. Como #L está contenido en DSPACE (log ^ 2 n), esto implicaría que # PSPACE = PSPACE, como @TsuyoshiIto mencionado anteriormente. (Estoy ignorando la distinción formal inmaterial entre problemas de decisión y funciones.)

Noam

Respuestas:

-3

El número de asignaciones satisfactorias a una fórmula booleana es igual al número de cuantificaciones válidas de la fórmula. La prueba inductiva es bastante elegante. Entonces #P = #PSpace.

daniel pehoushek
fuente

¿No está esto cubierto por los comentarios de Tsuyoshi y Noam anteriores?

Huck Bennett

\subseteq

$\subseteq$

^{# P}

$^{\#\mathrm{P}}$

@ PeterShor Estoy bastante seguro de que Daniel quiere decir esto mathoverflow.net/a/12608/35733 . Pero mi suposición (no verificada) es que un problema # PSPACE-complete es contar el número de asignaciones satisfactorias de un QBF fijo, no contar el número de cuantificaciones satisfactorias de un CNF determinado.

Sasho Nikolov

No, quise decir que el número de cuantificaciones válidas de un cnf dado es igual al número de asignaciones satisfactorias del cnf, dado un orden fijo de las variables. Es muy interesante porque cambiar el orden de las variables cambia los qbfs válidos, pero no el número total de qbfs válidos.

daniel pehoushek