Why is the counting variant of a hard decision problem not automatically hard?

Question

It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a problem for which decision is easy, but counting is hard.

But consider an arbitrary NP-complete problem (say 3-COL). Can we immediately say something about the hardness of its counting variant?

Really what I'm asking is: why do we need another proof to show a counting variant of a hard decision problem is also #P-hard? (Sometimes you see parsimonious reductions that preserve the number of solutions, and so on). I mean really, if the counting problem was easy, you could automatically solve the decision problem as well! So how could it not be hard? (OK, maybe it is hard, but I'm not sure for what definition of hard).

Answer 1

The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard".

• A decision problem is hard if it's NP-complete under polynomial-time many-one reductions (a.k.a. Karp reductions, a.k.a. polynomial-time mapping reductions).

• A counting problem is hard if it's #P-complete under polynomial-time Turing reductions (a.k.a. Cook reductions).

As such, if a decision problem is NP-complete, we know that the corresponding counting problem is NP-hard but that's not the definition of what a hard counting problem is. Being #P-complete seems to be a much stronger statement than just being NP-hard – Toda has shown that #P-complete problems are hard for the entire polynomial hierarchy under randomized reductions so, as a complexity class, #P feels much closer to PSPACE than to NP.

Going in the opposite direction, it's clearly true that, if the counting problem is easy in the sense of being in FP, then the decision problem is in P. After all, if you can efficiently count, you can certainly tell if the answer is nonzero. However, just because the counting version is "not hard" (i.e., not #P-complete) doesn't imply that it's "easy" (i.e., in FP). Ladner's theorem extends to #P so, if FP$\,\neq\,$**#P** then there's an infinite hierarchy of distinct complexity classes between them so our "not-hard" counting problem could be complete for any one of those classes and, therefore, not be "easy" (in FP).

Having said that, I don't think we have any counterexamples to the conjecture that a decision problem being NP-complete means that the counting version is #P-complete. So, it's not a theorem but it is empirically true.