対数空間の縮小

計算複雑性理論において、対数空間縮約とは、決定論的チューリングマシンが対数空間を使用して計算可能な縮約である。概念的には、これは、入力への一定数のポインタと、対数個の固定サイズの整数を保持できることを意味する。^[1] このようなマシンには独自の出力を書き込むスペースがない可能性があるため、唯一の要件は、出力の任意のビットが対数空間で計算可能であることです。正式には、この縮約は対数空間トランスデューサーを介して実行されます。

このようなマシンは多項式的に多くの構成を持つため、対数空間縮約は多項式時間縮約でもあります。ただし、対数空間縮約はおそらく多項式時間縮約よりも弱いです。P 内の任意の空でない非完全言語は、 P内の他の任意の空でない非完全言語に多項式時間縮約できますが、NL完全言語からL内の言語への対数空間縮約は、どちらも P 内の言語であるため、ありそうもない L = NL を意味します。NP完全問題が対数空間縮約と多項式時間縮約に関して異なる かどうかは未解決の問題です。

対数空間縮約は通常 P の言語で使用されますが、その場合、 L 、 SL、 NL 、および P はすべてチューリング縮約の下で閉じていることが検証されているため、多対一縮約を使用するかチューリング縮約を使用するかは通常は問題ではありません^{[引用が必要] 。つまり、チューリング縮約を使用して、問題がこれらのクラスのいずれかにあることを示すことができます。ただし、} NCなどの P の他のサブクラスはチューリング縮約の下で閉じていない可能性があるため、多対一縮約を使用する必要があります^{[引用が必要]}。

多項式時間縮約が P とそのサブクラス内で役に立たないのと同様に、対数空間縮約は L とそのサブクラスの問題を区別するのに役立ちません。特に、L 内の空でない、完全でないすべての問題は、対数空間縮約の下では自明に L完全です。さらに弱い縮約も存在しますが、L よりも小さい複雑性クラス (つまり、L に厳密に含まれるか、厳密に含まれると考えられる) は比較的あまり注目されないため、実際にはあまり使用されません。

L = SL という結果により、対数空間削減の設計者が利用できるツールが大幅に拡張されました。対数空間削減のサブルーチンとして使用できる SL 完全問題のリストについては、 SL を参照してください。

• Arora, Sanjeev ; Barak, Boaz (2009).計算複雑性。現代的なアプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4.ZBL1193.68112  。​

• Papadimitriou, Christos (1994)。「第 8 章: 縮約と完全性」。計算複雑性(第 1 版)。Addison Wesley。pp. 159–180。ISBN 0-201-53082-1.ZBL 0833.68049  .