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
es la función de conteo correspondiente y
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 puede reducirse a C Cook-reducido a # R (para el C apropiado ) usando una búsqueda binaria (la razón por la que # R se define de la forma en que es, en lugar de que ser la gráfica de c R , es hacer posible esta búsqueda binaria).
Contando la clase de complejidad
Si NX es una clase de complejidad asociada con máquinas no deterministas , entonces #X = { #R | R ∈ NX } es el conjunto de problemas de recuento asociados con cada problema de búsqueda en NX . En particular, #P es la clase de problemas de conteo asociados con problemas de búsqueda NP . Así como NP tiene problemas NP-completos a través de reducciones de muchos uno , #P tiene problemas completos a través de reducciones parsimoniosas , transformaciones de problemas que preservan el número de soluciones.