#P is the set of counting problems whose corresponding decision problem is in NP. Or more formally (from here): A function [math]f:left{0,1right}^*rightarrow mathbb{N}[/math] is in #[math]bf{P}[/math] if there exists a polynomial [math]p: mathbb{N}rightarrow mathbb{N}[/math] and a polynomial-time TM (turing machine) M such that for every [math]xin left{0,1right}^*[/math] [math]f(x)=left|{left{yin left{0,1right}^{p^{(|x|)}}:M(x,y)=1right}}right|[/math]. I later intend to find a proof or develop… Continue reading What is #P (Sharp P)