Sharp-P
計算複雑性理論において、複雑性クラス ♯P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。
NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。
ある整数のリストから部分集合を選んで、合計がゼロになるような組合せは存在するか? (部分和問題)
与えられたグラフで、コスト 100 以下のハミルトン路は存在するか? (巡回セールスマン問題)
与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せは存在するか? (充足可能性問題)
♯P 問題は、これらの「存在するか」の部分を「いくつ存在するか」に置き換えたものである。例えば、次のようなものがある。
ある整数のリストから部分集合を選んで、合計がゼロになるような組合せはいくつ存在するか?
与えられたグラフで、コスト 100 以下のハミルトン路はいくつ存在するか?
与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せはいくつ存在するか?