Numeral-P

clase de complejidad

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:

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

editar

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

editar
  1. Valiant, Leslie G. (1979). «The Complexity of Computing the Permanent». Theoretical Computer Science (Elsevier) 8 (2): 189-201. doi:10.1016/0304-3975(79)90044-6. 
  2. Valiant, Leslie G. (1979). «The complexity of enumeration and reliability problems». SIAM Journal on Computing (SIAM) 8 (3): 410-421. doi:10.1137/020803.