Problema de conteo (complejidad)

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Problema de conteo» complejidad – noticias  · periódicos  · libros  · académico  · JSTOR ( octubre de 2014 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En la teoría de la complejidad computacional y la teoría de la computabilidad , un problema de conteo es un tipo de problema computacional . Si R es un problema de búsqueda , entonces

${\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}$

es la función de conteo correspondiente y

${\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}$

denota el problema de decisión correspondiente.

Tenga en cuenta que c _R es un problema de búsqueda mientras que # R es un problema de decisión, sin embargo, c _R se puede reducir mediante C Cook a # R (para un C apropiado ) utilizando una búsqueda binaria (la razón por la que # R se define de la forma en que está, en lugar de ser el gráfico de c _R , es para hacer posible esta búsqueda binaria).

Así como NP tiene problemas NP-completos a través de reducciones de muchos-uno , #P tiene problemas #P-completos a través de reducciones parsimoniosas , transformaciones de problemas que preservan el número de soluciones. ^[1]

• Brecha

• "problema de conteo". PlanetMath .
• "clase de complejidad de conteo". PlanetMath .