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