真理値表の縮小

計算可能性理論において、真理値表還元は、決定問題から決定問題 への還元の一種です。 の問題を解決するために、還元は への答えを、への有限個のクエリのブール式または真理値表として記述します。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$

真理値表還元はチューリング還元と関連があり、厳密にはより弱いです。(つまり、集合間のすべてのチューリング還元が真理値表還元で実行できるわけではありませんが、すべての真理値表還元はチューリング還元で実行できます。) 集合Bから集合Aへのチューリング還元は、計算中にAのさまざまな要素のメンバーシップについて質問することにより、 Bの単一の要素のメンバーシップを計算します。以前の質問への回答に基づいて、どの質問をするかを適応的に決定する場合があります。対照的に、真理値表還元または弱い真理値表還元では、その (有限個の)オラクルクエリをすべて同時に提示する必要があります。真理値表還元では、クエリへの回答が与えられた場合に、還元の最終的な回答を生成するブール式(真理値表) も還元によって提供されます。

弱い真理値表還元とは、還元がオラクルの回答をさらなる計算の基礎として使用するもので、その計算は与えられた回答に依存する可能性があるが、オラクルにそれ以上の質問をしない可能性がある。これは、真理値表還元に課せられた制約を弱め、より弱い同値分類を提供することから、このように呼ばれている。そのため、「弱い真理値表還元」は、実際には「ツール」として真理値表還元よりも強力であり、真理値表では実行できない還元を実行することができる。同様に、弱い真理値表還元は、還元の使用が計算可能な関数によって制限されるチューリング還元である。このため、これらは弱い真理値表 (wtt) 還元ではなく、制限付きチューリング(bT) 還元と呼ばれることがある。

あらゆる真理値表還元はチューリング還元であるため、A がBに真理値表還元可能( A ≤ _tt B ) であれば、AはBにチューリング還元可能( A ≤ _T B ) である。1 対 1 還元可能性、多対 1 還元可能性、弱い真理値表還元可能性も考慮すると、

${\displaystyle A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B}$、

言い換えれば、一対一の還元可能性は多対一の還元可能性を意味し、それは真理値表の還元可能性を意味し、それは弱い真理値表の還元可能性を意味し、それはチューリング還元可能性を意味します。

さらに、A がB に真理値表還元可能であるのは、 Aが上の全関数を介してBにチューリング還元可能である場合のみです。順方向は自明であり、逆方向では が全計算可能関数であると仮定します。 A ( n )を計算するための真理値表を作成するには、長さmのすべてのバイナリ文字列について が収束するような数mを検索するだけです。は を通るすべてのパスで全でなければならないため、ケーニッヒの補題により、そのようなm が存在する必要があります。そのようなmが与えられれば、 に適用したときにとなる唯一の真理値表を見つけるのは簡単です。順方向は、弱い真理値表還元性では失敗します。 ${\displaystyle 2^{\omega}}$${\displaystyle \ガンマ}$${\displaystyle \sigma}$ ${\displaystyle \Gamma ^{\sigma }(n)}$${\displaystyle \ガンマ}$${\displaystyle 2^{<\omega}}$${\displaystyle \Gamma ^{\sigma }(n)}$${\displaystyle \sigma}$

• H. Rogers, Jr.、1967年。『再帰関数と効果的な計算可能性の理論』、第2版1987年、MIT Press。ISBN 0-262-68052-1 （ペーパーバック）、ISBN 0-07-053522-1