♯P

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

NP決定問題は多くの場合、「特定の制約を満たす解決策はあるか?」という形式になります。例:

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

対応する#P関数の問題では、「あるか」ではなく「いくつあるか」を尋ねます。例:

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

明らかに、#P問題は対応するNP問題と少なくとも同じくらい難しいはずです。答えを数えるのが簡単であれば、答えがあるかどうかを判断するのも簡単でなければなりません。答えを数えて、その数が 0 より大きいかどうかを確認するだけです。根を見つけるなどの一部の問題はFPになるほど簡単ですが、他の問題は#P 完全です。

戸田の定理の帰結の 1 つは、 #Pオラクル( P ^#P )を備えた多項式時間マシンは、多項式階層全体であるPH内のすべての問題を解くことができるということです。実際、多項式時間マシンは、PH内の任意の問題を解決するために 1 回の#Pクエリを実行するだけで済みます。これは、 #P完全問題を正確に解くことが極めて難しいことを示しています。

驚くべきことに、難しいと考えられているいくつかの#P問題は、簡単な (たとえば線形時間) P問題に対応しています。詳細については、#P 完全 を参照してください。

#Pに最も近い決定問題クラスはPPで、これは計算パスの過半数 (半分以上) が受け入れるかどうかを尋ねます。これは、#P問題の回答の最上位ビットを見つけます。決定問題クラス⊕P (「Parity-P」と発音) は、代わりに#P の回答の最下位ビットを尋ねます。

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

#Pは、すべての に対して が上の の計算グラフの受理枝の数に等しいような多項式時間非決定性チューリングマシンが存在するようなすべての関数の集合である。^[1]${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$ ${\displaystyle M}$${\displaystyle x\in \{0,1\}^{*}}$${\displaystyle f(x)}$${\displaystyle M}$${\displaystyle x}$

#P は検証者の観点からも同等に定義できます。与えられた問題インスタンスに対して多項式時間で検証可能な証明書が存在する場合、決定問題はNPに属します。つまり、NP は入力の正当性が多項式時間で検証可能なメンバーシップ証明が存在するかどうかを尋ねます。クラス#P は、問題インスタンスに対して多項式時間で正当性が検証可能な証明書がいくつ存在するかを尋ねます。[ 1 ^]このコンテキストでは、#P は次のように定義されます。

#Pは、多項式と、検証器と呼ばれる多項式時間の決定論的チューリングマシンが存在し、任意のに対してとなるような関数の集合です。^[2]（言い換えると、は多項式サイズの証明書をすべて含む集合のサイズに等しい）。${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$${\displaystyle p:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle V}$${\displaystyle x\in \{0,1\}^{*}}$${\displaystyle f(x)={\Big |}{\big \{}y\in \{0,1\}^{p(|x|)}:V(x,y)=1{\big \}}{\Big |}}$${\displaystyle f(x)}$

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

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

• Quantum_computing#Relation_to_computability_and_complexity_theory  – 量子力学を使用するコンピュータ ハードウェア テクノロジー

• 複雑性動物園：クラス #P