La razón por la cual no es un teorema automático de que "la decisión es difícil implica que contar es difícil" es que estas dos afirmaciones usan diferentes definiciones de "difícil".
Un problema de decisión es difícil si es NP- completo bajo reducciones de tiempo múltiple polinomial (también conocido como reducciones de Karp, también conocido como reducciones de mapeo de tiempo polinomial).
Un problema de conteo es difícil si es # P-completo bajo reducciones de Turing de tiempo polinomial (también conocido como reducciones de Cook).
Como tal, si un problema de decisión es NP- completo, sabemos que el problema de conteo correspondiente es NP -hard pero esa no es la definición de qué es un problema de conteo difícil. Siendo #P -Complete parece ser una declaración mucho más fuerte que acaba de ser NP -difícil - Toda ha demostrado que #P problemas -Complete son difíciles para toda la jerarquía polinómica bajo reducciones aleatorios así, como una clase de complejidad, #P siente mucho más cerca a PSPACE que a NP .
Va en la dirección opuesta, es verdad claramente que, si el problema de conteo es fácil en el sentido de estar en FP , entonces el problema de decisión está en P . Después de todo, si puede contar eficientemente, ciertamente puede decir si la respuesta es distinta de cero. Sin embargo, el hecho de que la versión de conteo sea "no difícil" (es decir, no #P -completa) no implica que sea "fácil" (es decir, en FP ). El teorema de Ladner se extiende a #P , entonces, si FP≠** # P ** entonces existe una jerarquía infinita de distintas clases de complejidad entre ellas, por lo que nuestro problema de conteo "no difícil" podría estar completo para cualquiera de esas clases y, por lo tanto, no ser "fácil" (en FP ).
Dicho esto, no creo que tengamos contraejemplos a la conjetura de que un problema de decisión sea NP- completo significa que la versión de conteo es #P -completa. Entonces, no es un teorema, pero es empíricamente cierto.