4
$\begingroup$

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?

$\endgroup$
  • $\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 '13 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$ – David Richerby Sep 28 '13 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 '13 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$ – David Richerby Sep 28 '13 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 '13 at 2:25
3
$\begingroup$

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$.

$\endgroup$
  • 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$ – Steven Stadnicki Sep 28 '13 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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