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:
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.
Escribe un comentario o lo que quieras sobre Numeral-P (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)