>415
NP は non-deterministically polynomial。

#P は大雑把に言うとものを数える、という問題のクラスで、
#P-complete は #P の中で完全
（その問題が多項式で解ければどの#P問題も多項式で解ける）
な問題の集合。
例えば SAT の式がいくつ解を持つか？という問題は #P-complete。

#P は NP よりも難しい。
NP は、答えが一つ以上あるかどうかを問う問題のクラスであり、
#P は答えがいくつあるかを問う問題のクラスだから。