2
$\begingroup$

I just read

  • J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

and one of the first sentences is

Valiant defines the notion of the #P-complete class (...) and shows that problems in this class are at least as hard as NP-complete problems.

My first problem is that is seems weird to directly compare the complexity of counting and decision problems. But more importantly: There are quite easy decision problems, whose counting variant is #P-complete, for example satisfiability of boolean formulas in DNF. This can also be read on Wikipedia:

http://en.wikipedia.org/wiki/Sharp-P-complete

So is the statement, that a #P-complete problem is at least as hard as a NP-complete problem simply wrong or am I getting something wrong?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ The statement means: "You can efficiently transform the inputs and use an algorithm $A$ that solves a #P-complete problem to solve an NPC problem $B$", i.e. $B \leq SAT \leq \#SAT \leq A$ (the time complexity is the same up to a polynomial overhead due to the first and third reductions, because the second one is simply a zero test). So $A$ cannot be easier than $B$ because it is itself a solver for $B$; i.e. as written by Valiant "$A$ is at least as hard as $B$". $\endgroup$
    – Marzio De Biasi
    Aug 30, 2014 at 9:59
  • 3
    $\begingroup$ Possibly, you are only acquainted with the concept of (polynomial) many-to-one reductions in which case comparing classes of languages and functions by reduction seems odd. If that is indeed the case then you should look up Turing reductions and the idea of oracles. With these concepts the mentioned reductions seem quite natural $\endgroup$
    – John D.
    Aug 30, 2014 at 11:59

1 Answer 1

Reset to default
6
$\begingroup$

It's not at all weird to compare the complexity of counting and decision problems: reductions allow you to do that very naturally. You can use reductions to compare any kind of problem: decision, counting, approximate counting, optimization, function problems, ... All of this follows from the intuitive notion that a reduction from A to B means "If I could solve B, I could also solve A at roughly the same cost."

The existence of easy decision problems whose counting version is hard is a red herring. Counting matchings is the hard problem: if you could do that, you could solve any NP problem by reduction. Detecting matchings is easy: you can do that but it doesn't (seem to) help you to solve NP-complete problems.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks, that clarified it. My mistake was to assume they were saying that the decision version of a problem is at least NP-complete if the counting version is #P-complete. $\endgroup$
    – Oliver Witt
    Aug 31, 2014 at 9:37
  • $\begingroup$ Yeah, your example of counting matchings shows that can't be the case. Also, note that even the converse isn't a theorem: because of the different notions of reduction (many-one for NP, polytime Turing for #P), it's not actually known that the decision problem being NP-complete implies that the counting problem is #P-complete. On the other hand, there are no known counterexamples and I don't think anyone believes there are any. $\endgroup$
    – David Richerby
    Aug 31, 2014 at 9:52
  • $\begingroup$ When we talk about the decision version of a counting problem, we mean: Is there any solution at all, right? What if we instead ask: Is there a solution set containing $k$ different solutions? Do we then have #P-completeness iff NP-completeness? $\endgroup$
    – Oliver Witt
    Sep 1, 2014 at 10:40
  • $\begingroup$ @OliverWitt Yes, by the decision version of a counting problem, I mean the problem "Is the answer to the counting problem nonzero?" The question "Is the answer to the counting problem at least $k$?" can be harder than this. For example, consider the following problem: the input is a Boolean formula $\varphi$ with $r$ variables and the output is the number of satisfying assignments to the formula $\varphi\vee (x_1\wedge\dots\wedge x_r)$. The decision version is easy (the answer is "yes"); the question "is the answer at least 2?" is NP-complete. $\endgroup$
    – David Richerby
    Sep 1, 2014 at 14:02
  • 1
    $\begingroup$ Yes, but again: Is it true that "How many solutions are there to problem $A$?" is #P-complete if and only if the question "Are there at least $k$ solutions to problem $A$?" is NP-complete? At least the one direction is quite easy: If I can tell how many solutions there are, I can of course answer the question whether there are at least $k$. However, if I can answer the question if there are at least $k$ solutions, how do I infer from that the exact number of solutions? $\endgroup$
    – Oliver Witt
    Sep 1, 2014 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.