多項式時間カウント削減

計数問題の計算複雑性理論において、多項式時間計数簡約は、計算複雑性クラス♯Pの完全性の概念を定義するために使用される簡約（ある問題から別の問題への変換）の一種である。^{[1]これらの簡約は、}多項式多対一計数簡約または弱節約簡約とも呼ばれる。これらは、決定問題に対する多対一簡約に類似しており、節約簡約を一般化したものである。^[2]

多項式時間カウンティングリダクションは、通常、既知の困難な問題のインスタンスを、困難であることが証明される別の問題のインスタンスに変換するために使用されます。これは、2 つの関数とで構成され、どちらも多項式時間で計算可能でなければなりません。関数は、の入力を の入力に変換し、関数はの出力を の出力に変換します。^{[1] [2]}${\displaystyle X}$${\displaystyle Y}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle g}$${\displaystyle Y}$${\displaystyle X}$

これら 2 つの関数は、出力の正確性を維持する必要があります。つまり、問題 の入力を問題 の入力に変換し、 を解いて出力 を生成するとします。変換された出力は、元の入力 に対する正しい出力である必要があります。つまり、との入出力関係が関数として表現される場合、それらの関数合成は恒等式に従わなければなりません。あるいは、アルゴリズムの観点から表現すると、 を解くための 1 つの可能なアルゴリズムは、を適用して問題を のインスタンスに変換し、そのインスタンスを解き、 を適用して の出力を の正しい答えに変換することです。^{[1] [2]}${\displaystyle x}$${\displaystyle X}$${\displaystyle y=f(x)}$${\displaystyle Y}$${\displaystyle y}$${\displaystyle z}$${\displaystyle g(z)}$${\displaystyle x}$${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle X=g\circ Y\circ f}$${\displaystyle X}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle g}$${\displaystyle Y}$${\displaystyle X}$

特別なケースとして、簡約縮約は、出力の正確な値を保存する問題への入力に対する多項式時間変換です。このような縮約は、恒等関数を関数として使用することで、多項式時間の計数縮約として見ることができます。^{[1] [2]}${\displaystyle f}$${\displaystyle g}$

関数型問題（入力と望ましい出力で指定）が複雑性クラス♯Pに属するのは、多項式時間で実行される非決定性チューリングマシンが存在し、その問題への出力がチューリングマシンの受理パスの数である場合です。直感的には、このような問題は複雑性クラスNPの問題の解の数を数えます。関数型問題が♯P 困難であるとは、 ♯P 内のすべての問題から への多項式時間の数え上げ還元が存在する場合です。さらに、自体が ♯P に属する場合、 は♯P 完全であると言われます。^{[1] [2] （} 0–1 行列のパーマネントの完全性を証明したValiant の元の論文のように、より弱い還元の概念であるチューリング還元が ♯P 完全性の定義に使用されることもあります。^[3]） ${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle Y}$

♯P の問題が ♯P 完全であることを証明する通常の方法は、既知の ♯P 完全問題を 1 つ用意し、 から への多項式時間の計数還元を見つけることです。この還元が存在する場合、他の問題から への還元と からへの還元を合成することで得られる、♯P の他の任意の問題から への還元も存在します。^{[1] [2]}${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$${\displaystyle Y}$