ヴァイラウフ還元性

計算解析において、ヴァイラウフ還元可能性とは、表現空間上の多価関数間の還元可能性の概念であり、計算問題の均一な計算力を大まかに捉えたものである。^[1]これは、1992年にクラウス・ヴァイラウフによって未発表の技術レポートで最初に導入された。^[2]

表現空間は集合と射影的部分関数の ペアである。[ ^1]${\textstyle (X,\delta )}$${\displaystyle X}$ ${\displaystyle \delta :\subset \mathbb {N} ^{\mathbb {N} }\rightarrow X}$

と を空間として表現し、 を部分多価関数とします。の実現子は、任意のに対してとなる(場合によっては部分的な) 関数です。直感的には、の実現子は「 とまったく同じように」動作しますが、名前に対して動作します。 がの実現子である場合、と書きます。 ${\displaystyle (X,\delta _{X})}$${\displaystyle (Y,\delta _{Y})}$${\displaystyle f:\subset X\rightrightarrows Y}$${\displaystyle f}$${\displaystyle F:\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}$${\displaystyle p\in \mathrm {dom} f\circ \delta _{X}}$${\displaystyle \delta _{Y}\circ F(p)=f\circ \delta _{X}(p)}$${\displaystyle F}$${\displaystyle f}$${\displaystyle f}$${\displaystyle F}$${\displaystyle f}$${\displaystyle F\vdash f}$

が表現空間であり、が部分多価関数であるとします。 が にヴァイラウフ還元可能であるといい、 となる計算可能な部分関数が存在する場合、 と書きます。ここで、 およびはベール空間における結合を表します。文献では、結合の使用を避けるために、 がバイナリ関数として記述されることがよくあります。^[要出典]言い換えると、が の解であるときはいつでも、関数 がの実現子となるような計算可能なマップが 2 つある場合です。マップは、それぞれ順方向関数と逆方向関数 と呼ばれることがよくあります。${\displaystyle X,Y,Z,W}$${\displaystyle f:\subset X\rightrightarrows Y,g:\subset Z\rightrightarrows W}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f\leq _{\mathrm {W} }g}$${\displaystyle \Phi ,\Psi :\subset \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} ^{\mathbb {N} }}$$${\displaystyle (\forall G\vdash g)(\Psi \langle \mathrm {id} ,G\Phi \rangle \vdash f),}$$${\displaystyle \Psi \langle \mathrm {id} ,G\Phi \rangle :=\langle p,q\rangle \mapsto \Psi (\langle p,G\Phi (q)\rangle )}$${\displaystyle \langle \cdot \rangle }$${\displaystyle \Psi}$${\displaystyle f\leq _{\mathrm {W} }g}$${\displaystyle \Phi ,\Psi }$${\displaystyle p\mapsto \Psi (p,q)}$${\displaystyle f}$${\displaystyle q}$${\displaystyle g(\Phi (p))}$${\displaystyle \Phi ,\Psi }$

は に強くヴァイラウフ還元可能であると言い、逆関数が元の入力にアクセスできない場合はと書きます。記号で表すと、${\displaystyle f}$${\displaystyle g}$${\displaystyle f\leq _{\mathrm {sW} }g}$${\displaystyle \Psi}$$${\displaystyle (\forall G\vdash g)(\Psi G\Phi \vdash f).}$$

• ワッジ還元可能性