# counting complexity class

If $\mathcal{NC}$ is a complexity class associated with non-deterministic machines then $\mathcal{\#C}=\{\#R\mid R\in\mathcal{NC}\}$ is the set of counting problems associated with each search problem in $\mathcal{NC}$. In particular, $\mathcal{\#P}$ is the class of counting problems associated with $\mathcal{NP}$ search problems.

Title counting complexity class CountingComplexityClass 2013-03-22 13:02:31 2013-03-22 13:02:31 Henry (455) Henry (455) 4 Henry (455) Definition msc 68Q15