Sharp-P
提供: miniwiki
計算複雑性理論において、複雑性クラス ♯P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。
NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。
- ある整数のリストから部分集合を選んで、合計がゼロになるような組合せは存在するか? （部分和問題）
- 与えられたグラフで、コスト 100 以下のハミルトン路は存在するか? （巡回セールスマン問題）
- 与えられた連言標準形の論理式を満足する（真とする）変数の値の組合せは存在するか? （充足可能性問題）
♯P 問題は、これらの「存在するか」の部分を「いくつ存在するか」に置き換えたものである。例えば、次のようなものがある。
- ある整数のリストから部分集合を選んで、合計がゼロになるような組合せはいくつ存在するか?
- 与えられたグラフで、コスト 100 以下のハミルトン路はいくつ存在するか?
- 与えられた連言標準形の論理式を満足する（真とする）変数の値の組合せはいくつ存在するか?
より形式的に言えば、♯P は函数問題のクラスであり、「f(x)を計算せよ」という形式である。ここで f は、ある NP 機械の受容経路数を与える函数である。
明らかに、♯P 問題は対応する NP 問題よりも難しい。解を数え上げるのが簡単なら、解があるかどうかを知るのはもっと簡単なはずである。従って、NP完全問題に対応した ♯P 問題は、NP困難となる。
驚くべきことに、一部の難しいといわれる ♯P 問題は、比較的易しい P 問題に対応したものである。
♯P に最も近い決定問題は PP である。これは、計算経路の多数（半分以上）が受理されるかどうかを問うものである。つまりこれは ♯P 問題の答えの最上位ビットに対応している。決定問題クラス ⊕P は、逆に ♯P の答えの最下位ビットを答えとするものである。
戸田の定理の結論の1つとして、多項式時間機械に ♯P 神託機械を付与したもの（P♯P）は PHに属する全問題（多項式階層全体）を解くことができる。実際、多項式時間機械は1回だけ ♯P の神託を受けるだけで PH に属する任意の問題に答えることができる。これは、♯P完全な問題を解くことが非常に困難であることを如実に示している。