♯P

En la teoría de la complejidad computacional, la clase de complejidad #P (pronunciada "sharp P" o, a veces, "number P" o "hash P& #34;) es el conjunto de problemas de conteo asociados con los problemas de decisión en el conjunto NP. Más formalmente, #P es la clase de problemas de funciones de la forma "calcular f(x)", donde f es el número de caminos de aceptación de una máquina de Turing no determinista que se ejecuta en tiempo polinomial. A diferencia de la mayoría de las clases de complejidad conocidas, no es una clase de problemas de decisión sino una clase de problemas de funciones. Los problemas representativos más difíciles de esta clase son #P-completos.

Relación con problemas de decisión

Un problema de decisión NP suele tener la forma "¿Existen soluciones que satisfagan ciertas restricciones?" Por ejemplo:

• ¿Hay subconjuntos de una lista de enteros que suman hasta cero? (Problema de la suma de activos)
• ¿Hay algún ciclo Hamiltoniano en un gráfico dado con menos de 100? (Traveling salesman problem)
• ¿Hay alguna asignación variable que satisfaga una fórmula de CNF (forma normal conjuntiva) dada? (Problema de satisfiabilidad booleana o SAT)
• ¿Tiene una polinomía real univariada raíces positivas? (Recuperación de raíces)

Los problemas correspondientes de la función #P preguntan "cuántos" en lugar de "hay alguno". Por ejemplo:

• ¿Cuántos subconjuntos de una lista de enteros suman hasta cero?
• ¿Cuántos ciclos Hamiltonianos en un gráfico dado han costado menos de 100?
• ¿Cuántas asignaciones variables satisfacen una fórmula CNF dada?
• ¿Cuántas raíces de un polinomio real univariado son positivas?

Clases de complejidad relacionadas

Claramente, un problema #P debe ser al menos tan difícil como el problema NP correspondiente. Si es fácil contar las respuestas, entonces debe ser fácil saber si hay alguna respuesta; solo cuéntelas y vea si el conteo es mayor que cero. Algunos de estos problemas, como la búsqueda de raíces, son lo suficientemente fáciles como para estar en FP, mientras que otros son #P-completos.

Una consecuencia del teorema de Toda es que una máquina del tiempo polinomial con un oráculo #P (P^#P) puede resolver todos los problemas en PH, toda la jerarquía de polinomios. De hecho, la máquina del tiempo polinomial solo necesita realizar una consulta #P para resolver cualquier problema en PH. Esta es una indicación de la extrema dificultad de resolver exactamente problemas #P-completos.

Sorprendentemente, algunos problemas #P que se consideran difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal). Para obtener más información al respecto, consulte #P-complete.

La clase de problema de decisión más cercana a #P es PP, que pregunta si la mayoría (más de la mitad) de las rutas de cálculo aceptan. Esto encuentra el bit más significativo en la respuesta del problema #P. En cambio, la clase de problema de decisión ⊕P (pronunciado "Parity-P") solicita el bit menos significativo de la respuesta #P.

Definiciones formales

#P se define formalmente de la siguiente manera:

#P es el conjunto de todas las funciones f:{}0,1}Alternativa Alternativa → → N{displaystyle f:{0,1}{*}to mathbb {N} tal que hay un tiempo polinomio no determinista Máquina de tortuga M{displaystyle M} tal que para todos x▪ ▪ {}0,1}Alternativa Alternativa {displaystyle xin {0,1} {}}} {}}, f()x){displaystyle f(x)} iguala el número de ramas aceptadas en M{displaystyle M}'s gráfico de computación en x{displaystyle x}.

#P también se puede definir de manera equivalente en términos de un verificador. Un problema de decisión está en NP si existe un certificado verificable de tiempo polinomial para una instancia de problema dada, es decir, NP pregunta si existe una prueba de membresía para la entrada cuya corrección se puede comprobar en tiempo polinomial. La clase #P pregunta cuántos certificados existen para una instancia de problema cuya corrección se puede verificar en tiempo polinomial. En este contexto, #P se define de la siguiente manera:

#P es el conjunto de funciones f:{}0,1}Alternativa Alternativa → → N{displaystyle f:{0,1}{*}to mathbb {N} tal que exista un polinomio p:N→ → N{displaystyle p:mathbb {N} to mathbb {N} y una máquina de Turing determinista de tiempo polinomio V{displaystyle V}, llamado el verificador, tal que para cada x▪ ▪ {}0,1}Alternativa Alternativa {displaystyle xin {0,1} {}}} {}}, f()x)=Silencio{}Sí.▪ ▪ {}0,1}p()SilencioxSilencio):V()x,Sí.)=1}Silencio{fnMicrosoft Sans Serif}{big{}yin {0,1}^{p(Principalidad)}:V(x,y)=1{big {fnK}}. (En otras palabras, f()x){displaystyle f(x)} iguala el tamaño del conjunto que contiene todos los certificados de tamaño polinomio).

Historia

La clase de complejidad #P fue definida por primera vez por Leslie Valiant en un artículo de 1979 sobre el cálculo del permanente de una matriz cuadrada, en el que demostró que el permanente es #P-completo.

Larry Stockmeyer ha probado que por cada problema #P P{displaystyle P} existe un algoritmo aleatorizado usando un oráculo para SAT, que dio una instancia a{displaystyle a} de P{displaystyle P} y 0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle epsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/568095ad3924314374a5ab68fae17343661f2a71" style="vertical-align: -0.338ex; width:5.205ex; height:2.176ex;"/> retornos con alta probabilidad un número x{displaystyle x} tales que ()1− − ε ε )P()a)≤ ≤ x≤ ≤ ()1+ε ε )P()a){displaystyle (1-epsilon)P(a)leq xleq (1+epsilon)P(a)}. El tiempo de ejecución del algoritmo es polinomio en a{displaystyle a} y 1/ε ε {displaystyle 1/epsilon }. El algoritmo se basa en el hash lemma sobrante.