Wiki (http://en.wikipedia.org/wiki/Sharp-P) says 'In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP'.

Is there a counting version for CoNP problems?

  • $\begingroup$ #P can count the number of accepting paths in a TM. Hence, not only you're able to know if there is at least one accepting path (for NP), but you can also check that all paths are accepting (for coNP). Hence #P is associated with both NP and coNP. $\endgroup$
    – Tpecatte
    Sep 27, 2013 at 22:21
  • 1
    $\begingroup$ It would perhaps be better to say that #P is the set of counting problems associated with polynomial-time nondeterministic Turing machines, rather than with NP specifically. $\endgroup$ Sep 28, 2013 at 0:01
  • 1
    $\begingroup$ It's usually pronounced "sharp P". I believe the coiner of this notation intended it to be pronounced "number P", but he neglected to specify the pronunciation in his paper. But at least it's not pronounced "octothorpe P". $\endgroup$
    – Peter Shor
    Sep 28, 2013 at 1:07
  • 1
    $\begingroup$ @PeterShor "Sharp P" seems to be more common in North America; "Number P" in Europe. My own feeling is that it makes much more sense to use the pronunciation that describes what the class does, rather than describing the notation. (After all, we say "Parity-P", not "Plus-sign-in-a-circle-P".) $\endgroup$ Sep 28, 2013 at 2:19
  • $\begingroup$ one can count the # of solutions of decision problems of any complexity class (its like an operator applied to a complexity class), but some are more obscure than others. $\endgroup$
    – vzn
    Sep 28, 2013 at 2:25

1 Answer 1


Expanding on Timot's comment, $\# P$ consists of all functions which can be expressed as the number of accepting computations of some non-deterministic Turing machine running in polynomial time. It is also the class of all functions which can be expressed at the number of non-accepting computations of some non-deterministic Turing machine running in polynomial time (exercise).

If $f \in \# P$ then $\{ x : f(x) \geq 1 \} \in N\! P$ and $\{x : f(x) = 0 \} \in \mathrm{co}N\! P$; and vice versa, if $L \in N\!P$ ($L \in \mathrm{co}N\!P$) then it can be expressed in the form $\{ x : f(x) \geq 1 \}$ ($\{ x : f(x) = 0 \}$) for some $f \in \# P$.

  • 2
    $\begingroup$ (But note that the difference between the number of accepting and the number of non-accepting computations is not necessarily in #P, of course) $\endgroup$ Sep 28, 2013 at 0:00

Your Answer

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

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