計算複雑性理論において、複雑性クラス #P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。より形式的に言えば、#P は函数問題のクラスであり、「f(x)を計算せよ」という形式である。ここで f は、ある NP 機械の受容経路数を与える函数である。明らかに、#P 問題は対応する NP 問題よりも難しい。解を数え上げるのが簡単なら、解があるかどうかを知るのはもっと簡単なはずである。従って、NP完全問題に対応した #P 問題は、NP困難となる。驚くべきことに、一部の難しいといわれる #P 問題は、比較的易しい P 問題に対応したものである。戸田の定理の結論の1つとして、多項式時間機械に #P 神託機械を付与したもの（P）は PHに属する全問題（多項式階層全体）を解くことができる。実際、多項式時間機械は1回だけ #P の神託を受けるだけで PH に属する任意の問題に答えることができる。これは、#P完全な問題を解くことが非常に困難であることを如実に示している。

出典:wikipedia