Numeral-P

En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral-P) es el conjunto de los problemas de conteo asociados a los problemas de decisión en el conjunto NP.

Un problema en NP se describe usualmente con la pregunta ¿Existe una solución que satisface una cierta restricción?, por ejemplo:

• ¿Existe algún subconjunto de enteros cuya suma de elementos sea cero? (Problema de suma de subconjuntos)
• ¿Existe algún ciclo Hamiltoniano en un grafo dado con costo inferior a 100? (Problema del agente viajero)
• ¿Existe alguna asignación de variables que satisfaga una expresión booleana? (Problema de satisfacibilidad booleana)

Los problemas correspondientes en #P se interesan en saber cuantos elementos satisfacen la pregunta en lugar de si existe algún elemento que la satisfaga. Por ejemplo:

• ¿Cuántos subconjuntos de enteros tiene un conjunto cuya suma de elementos sea cero?
• ¿Cuántos ciclos Hamiltonianos en un grafo tienen costo inferior a 100?
• ¿Cuántas asignaciones de variables satisfacen una fórmula dada?

Más formalmente, un problema pertenece a #P si existe una máquina de Turing no determinista que en tiempo polinómico obtiene para cada instancia I el número de soluciones diferentes que validan a I.

Claramente, un problema de #P tiene que ser más costoso que el correspondiente problema en NP. Si es fácil contar las respuestas, también lo es el responder si existe alguna, verificando si la cuenta es mayor a cero. Por ello el problema correspondiente a un problema NP-completo tiene que ser NP-hard.

Historia

La clase de complejidad #P fue inicialmente definida por Leslie Valiant en un artículo de 1979 donde demuestra que calcular la permanente de una matriz cuadrada es un problema #P-completo.^[1]​ Ese mismo año, publicó otro artículo demostrando la #P-completitud de diversos problemas computacionales.^[2]​

Referencias