多対一還元

多対一還元（Many-One Reduction）

多対一還元とは、計算理論および計算量理論における特定のタイプの還元操作のことを指します。この操作は、ある決定問題を別の決定問題に変換する能力を持っています。これは、複雑さの比較や問題の解法を探求する際に非常に重要な役割を果たします。

多対一還元は特にチューリング還元の一種であり、チューリング還元よりも制約が強いとされます。この還元方式では、オラクルの機能は一回だけ、最後に許可されるため、計算の過程での柔軟性が外部サポートを必要としない範囲に制限されます。

この概念は1944年にエミール・ポストによって初めて提唱され、その後1956年にはノーマン・シャピロが同様のアイデアを「strong reducibility」という名称で広めました。

定義

数学的には、形式言語AおよびBをそれぞれアルファベットの集合ΣおよびΓのもとで考えます。AからBへの多対一還元は、特定の全体計算可能関数f: Σ → Γが存在し、以下の条件を満たすことを意味します：個々の単語wがAに含まれる必要十分条件は、変換後のf(w)がBに含まれることです。これにより、AはBに対して多対一還元可能であるとされ、通常次のように表記されます。

A ≤

m B

同様に、もしAからBへの単射な多対一還元が存在する場合、AはBに対して1-還元可能であると言います。

自然数の部分集合

二つの集合A、Bが自然数の部分集合であるとき、全体計算可能関数fが存在して、A = f^{-1}[B]が成り立つ場合、AはBに多対一還元可能と表現されます。この追加条件として、関数fが単射である場合、AはBに1-還元可能とされます。

多対一同値と1-同値

A ≤

m BかつB ≤

m Aが成り立つ場合、AとBは多対一同値(m-同値)であると言い、次のように表記されます。

A ≡ m B

同様に、A ≤

1 BかつB ≤

1 Aであるとき、AはBに1-同値であると表現されます。

多対一完全性（m-完全性）

ある帰納的可算集合Bがあり、すべての帰納的可算集合AがBに多対一還元可能な場合、Bは多対一完全またはm-完全であると称されます。この概念は、計算可能性の理論において特に興味深いものです。

資源制限付きの多対一還元

多対一還元は、計算資源の制約と関連付けられることが多いです。例えば、還元関数が多項式時間や対数空間で計算可能であるかどうかという点も考慮されます。これは、問題の解決効率に直結する重要な要素です。

さらに、決定問題AとBの概念を利用して、Bを解決できるアルゴリズムNがあった場合、Nを用いてAをBに多対一還元することでAも解決できることになります。このときのコストは、Nを実行するために必要な時間や領域に加え、還元に要する時間や領域が含まれることになります。

多対一還元のクラス

ある言語クラスCに含まれない言語をCに含まれる言語に多対一還元できないとき、Cは「多対一還元の下で閉じている」と言います。Cがこの条件を満たす場合、Cに住む問題を他の問題に多対一還元できると、その還元もとの問題はCに含まれるということになります。このようなクラスには、P、NP、L、NL、co-NP、PSPACE、またはEXPTIMEなどが含まれますが、必ずしもすべての多対一還元の下で閉じているわけではありません。

性質

多対一還元および一対一還元は、推移的かつ反射的であり、したがって自然数の冪集合に対して半順序を形成します。ある集合が停止問題に多対一還元可能な必要十分条件は、その集合が帰納的可算集合であることです。これにより、停止問題が多対一完全であることが示されます。特定のチューリングマシンに対する停止問題が多対一完全であるためには、そのチューリングマシンが万能であることが条件です。

エミール・ポストは、決定可能でもm-完全でもない帰納的可算集合が存在することを示し、これにより、特定の停止問題が決定不可能である万能でないチューリングマシンが存在することが確認されました。

もう一度検索