A razão pela qual não é um teorema automático de que "a decisão é difícil implica que a contagem é difícil" é que essas duas declarações usam definições diferentes de "difícil".
Um problema de decisão é difícil se for NP- completo sob reduções polinomiais de muitas-uma (também conhecidas como reduções de Karp, também conhecidas como reduções de mapeamento de tempo polinomial).
Um problema de contagem é difícil se for #P completo com reduções de Turing em tempo polinomial (também conhecidas como reduções de Cook).
Assim, se um problema de decisão for NP- completo, sabemos que o problema de contagem correspondente é NP- difícil, mas essa não é a definição do que é um problema de contagem-difícil. Ser completo #P parece ser uma afirmação muito mais forte do que apenas ser NP - duro - Toda mostrou que os problemas completos #P são difíceis para toda a hierarquia polinomial sob reduções aleatórias, portanto, como uma classe de complexidade, o #P se sente muito mais próximo para PSPACE do que para NP .
Indo na direção oposta, é claramente verdade que, se o problema de contagem é fácil, no sentido de estar em FP , então o problema de decisão está em P . Afinal, se você puder contar com eficiência, certamente poderá dizer se a resposta é diferente de zero. No entanto, apenas porque a versão da contagem "não é difícil" (ou seja, não é # P- completa) não implica que seja "fácil" (ou seja, no FP ). O teorema de Ladner se estende a #P , então, se FP ** # P **, existe uma hierarquia infinita de classes de complexidade distintas entre elas, para que o nosso problema de contagem "não-difícil" possa estar completo para qualquer uma dessas aulas e, portanto, não ser "fácil" ≠
Dito isto, não creio que tenhamos contra-exemplos de que um problema de decisão seja NP- completo significa que a versão de contagem é # P- completa. Portanto, não é um teorema, mas é empiricamente verdadeiro.
