＃P

計算複雑性理論において、計算複雑性クラス#P (「シャープ P」、あるいは「ナンバー P」や「ハッシュ P」と発音される) は、集合NP内の決定問題に関連付けられた計数問題の集合である。より正式には、#Pは「 f ( x ) を計算する」という形式の関数問題のクラスであり、ここでfは多項式時間で実行される非決定性チューリングマシンの受理パスの数である。よく知られているほとんどの計算複雑性クラスとは異なり、これは決定問題のクラスではなく、関数問題のクラスである。このクラスの最も困難で代表的な問題は、#P 完全である。

意思決定問題との関係

NP決定問題は、多くの場合、「特定の制約を満たす解決策は存在するか」という形式で表現されます。たとえば、次のようになります。

合計が 0 になる整数のリストの部分集合はありますか? (部分集合の和の問題)
与えられたグラフにはコストが 100 未満のハミルトンサイクルがありますか? (巡回セールスマン問題)
与えられたCNF（連言正規形）式を満たす変数割り当ては存在するか？（ブール充足可能性問題またはSAT）
一変数実多項式には正の根がありますか? (根を求める)

対応する#P関数の問題では、「あるか」ではなく「いくつあるか」を問うことになります。例えば：

整数のリストの部分集合の合計がゼロになるものはいくつありますか?
特定のグラフ内のハミルトンサイクルのうち、コストが 100 未満のものはいくつありますか?
与えられた CNF 式を満たす変数割り当てはいくつありますか?
一変数実多項式の根のうち、正になるものはいくつありますか?

正式な定義

#Pは正式には次のように定義されます。

#Pは、すべてのに対しての計算グラフにおける受理枝の数に等しい、多項式時間非決定性チューリングマシンが存在するような関数全体の集合である。^[¹^]

f:\{0,1\}^{*}\to \mathbb {N}

M

x\in \{0,1\}^{*}

f(x)

M

x

#P は検証者を用いて同様に定義することもできる。ある決定問題がNPに属するとは、与えられた問題インスタンスに対して多項式時間で検証可能な証明書が存在する場合である。つまり、NP は入力の正しさが多項式時間で検証可能なメンバーシップ証明が存在するかどうかを問う。#Pにおける問いは、ある問題インスタンスに対して多項式時間で正しさが検証可能な証明書がいくつ存在するかを問うものである。 ^{[ 1 ]}この文脈において、#Pは以下のように定義される。

#Pは、多項式と、検証器と呼ばれる多項式時間の決定論的チューリングマシンが存在し、任意のに対してとなるような関数の集合である。^[²^]（言い換えると、は多項式サイズの証明書をすべて含む集合のサイズに等しい）。

f:\{0,1\}^{*}\to \mathbb {N}

p:\mathbb {N} \to \mathbb {N}

V

x\in \{0,1\}^{*}

f(x)={\Big |}{\big \{}y\in \{0,1\}^{p(|x|)}:V(x,y)=1{\big \}}{\Big |}

f(x)

歴史

計算量クラス#Pは、1979年の正方行列のパーマネントの計算に関する論文でレスリー・ヴァリアントによって初めて定義され、パーマネントが#P完全であることを証明した。^[³^]

ラリー・ストックマイヤーは、あらゆる#P問題に対して、SATのオラクルを用いたランダム化アルゴリズムが存在することを証明した。このアルゴリズムは、とのインスタンスが与えられると、高い確率でとなる数を返す。^[⁴^] このアルゴリズムの実行時間はとの多項式である。このアルゴリズムは、残余ハッシュ補題に基づいている。 $P$ $a$ $P$ $\epsilon >0$ $x$ $(1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)$ $a$ $1/\epsilon$