Numeral-P

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.