SL（複雑さ）

計算複雑性理論において、SL (対称対数空間またはSym-L ) は、USTCON (無向対数接続)に対数空間還元可能な問題の複雑性クラスであり、無向グラフの2つの頂点間にパスが存在するかどうかを判断する問題、または2つの頂点が同じ接続コンポーネント内にあるかどうかを判断する問題として説明されます。この問題は、無向到達可能性問題とも呼ばれます。多対一還元可能性とチューリング還元可能性のどちらを使用するかは問題ではありません。もともと対称チューリングマシンの観点から説明されていましたが、それと同等の定式化は非常に複雑であり、実際には還元可能性の定義が使用されます。

USTCON は、有向グラフ内の 2 つの頂点間に有向パスが存在するかどうかを判断する問題であるSTCON (有向到達可能性)の特殊なケースであり、 NLに対して完全です。 USTCON はSL完全であるため、 USTCON に影響を与える進歩のほとんどはSL にも影響を与えています。したがって、これらは関連しており、一緒に議論されます。

2004 年 10 月、Omer Reingold はSL = Lであることを示しました。

SLは1982年にハリー・R・ルイスとクリストス・パパディミトリウ^[1]によって初めて定義されました。彼らはUSTCONを配置するクラスを探していましたが、このクラスは非決定性を必要としないように見えたにもかかわらず、この時点ではせいぜいNLにしか配置できませんでした。彼らは対称チューリングマシンを定義し、それを使用してSLを定義し、USTCONがSLに対して完全であることを示し、

${\displaystyle {\mathsf {L}}\subseteq {\mathsf {SL}}\subseteq {\mathsf {NL}}}$

ここで、L は、対数空間で通常の決定性チューリング マシンによって解決可能な、よりよく知られた問題のクラスであり、NL は、対数空間で非決定性チューリング マシンによって解決可能な問題のクラスです。後で説明するラインゴールドの結果は、実際には、対数空間に限定すると、対称チューリング マシンの能力は決定性チューリング マシンと同等であることを示しています。

定義により、USTCON は SL に対して完全です (SL のすべての問題は、USTCON 自体も含めて USTCON に帰着します)。USTCON から直接的または間接的に帰着した興味深い完全な問題が数多く発見され、Àlvarez と Greenlaw によってそれらの概要が作成されました。^[2]問題の多くは無向グラフ上のグラフ理論の問題です。彼らが説明する最も単純で最も重要な SL 完全問題には次のものがあります。

• USTCON
• 対称チューリング マシンのシミュレーション: STM は、単項で指定された特定の空間内の特定の入力を受け入れますか?
• 頂点が互いに素なパス: 2 つの頂点の間に、端点でのみ頂点を共有するk本のパスがありますか? (USTCON の一般化、グラフがk接続されているかどうかを尋ねることと同等)
• 与えられたグラフは二部グラフでしょうか、あるいは、2 色を使用したグラフ色付けがあるのでしょうか?
• 2 つの無向グラフには、同じ数の連結要素がありますか?
• グラフには偶数個の接続コンポーネントがありますか?
• グラフが与えられた場合、与えられたエッジを含むサイクルは存在しますか?
• 2 つのグラフの全域森には同じ数のエッジがありますか?
• すべての辺が異なる重みを持つグラフが与えられた場合、与えられた辺は最小重み全域森内にあるでしょうか?
• 排他的または2 の充足可能性:またはが複数の変数のペアに対して成立することを要求する式が与えられた場合、それを真にする変数への割り当てがあるか?${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle (x_{i},x_{j})}$

これらすべての問題の補集合も SL に存在します。これは、後で説明するように、SL が補集合に関して閉じているためです。

L = SLであるという事実から、対数空間削減に関して SL 完全である問題はさらに多くあることがわかります。つまり、 LまたはSL内のすべての非自明な問題はSL完全です。さらに、削減がLよりも小さいクラスにある場合でも、L完全性はSL完全性と同等です。この意味で、このクラスはいくぶん自明になっています。

USTCON を線形時間と空間で解く、深さ優先探索や幅優先探索などのよく知られた古典的なアルゴリズムがあります。 SL が定義されるずっと前から示されているこれらのアルゴリズムの存在は、SL がPに含まれることを証明しています。 また、USTCON が、そしてSLがNLに含まれることを示すことも難しくありません。なぜなら、パスが存在する場合は、パスを発見するために、各頂点で次にどの頂点を訪問するかを非決定論的に推測すればよいからです。

しかし、SLの最初の非自明な結果は、1970年に証明されたサビッチの定理であり、これはUSTCONをlog ² n空間で解くアルゴリズムを提供しました。しかし、深さ優先探索とは異なり、このアルゴリズムは実行時間が超多項式になる可能性があるため、ほとんどのアプリケーションでは実用的ではありません。この結果の1つは、USTCON、そしてSLがDSPACE (log ² n )に含まれることです。^{[3] （実際には、サビッチの定理は、} NLがDSPACE (log ² n )に含まれるというより強い結果を示しています。）

22年間、Savitchのアルゴリズムに対する（一様）決定論的空間の改良は行われなかったが、1979年にAleliunasらによって非常に実用的な確率的対数空間アルゴリズムが発見された。これは、単純に1つの頂点から始めて、他の頂点が見つかるまで（受け入れる）、または| V | ³時間が経過するまで（拒否する）ランダムウォークを実行するというものである。 ^[4]誤った拒否は小さな有界確率で行われ、ランダムウォークが長く続くほど、指数関数的に減少する。これは、SLが、誤って拒否する確率マシンが1/3未満の時間で多項式時間と対数空間で解決可能な問題のクラスであるRLPに含まれていることを示した。Aleliunasらは、ランダムウォークをユニバーサルトラバーサルシーケンスに置き換えることで、SLが、多項式アドバイスを使用して対数空間で決定論的に解決可能な問題の非一様複雑性クラスであるL/polyに含まれていることも示した。

1989年、ボロディンらは、2つの頂点が異なる連結成分に属するかどうかを判断するUSTCONの補集合もRLPに含まれることを示して、この結果を補強した。^[5]これにより、USTCONとSLはco- RLPに含まれるようになり、 RLPとco- RLPの共通部分であるZPLPにも含まれるようになった。ZPLPは、対数空間、期待多項式時間、エラーのないランダム化アルゴリズムを持つ問題のクラスである。

1992年、Nisan、Szemerédi、Wigdersonはついに、 ^log1.5n 空間のみを使用してUSTCONを解く新しい決定論的アルゴリズムを発見しました。^{[6]これはわずかに改善されましたが、Reingoldが登場するまで、それ以上の大きな進歩}はありませんでした。

1995年、ニサンとタシュマは、SLが補集合に関して閉じているという驚くべき結果を示したが、当時は多くの人がこれは誤りであると信じていた。つまり、SL = co- SLである。^[7]同様に、ある問題をグラフに縮小し、2つの頂点が同じコンポーネントにあるかどうかを尋ねることで解決できる場合、別のグラフに縮小し、2つの頂点が異なるコンポーネントにあるかどうかを尋ねることでも解決できます。しかし、後にラインゴールドの論文によってこの結果は不要になりました。

SL = co- SLの最も重要な帰結の 1 つは、 L ^SL = SLであることです。つまり、SLのオラクルを持つ決定論的な対数空間マシンは、 SLの問題を (自明に) 解決できますが、他のいかなる問題も解決できません。これは、問題がSLにあることを示すためにチューリング還元性を使用するか、多対一還元性を使用するかは問題ではなく、それらは同等であることを意味します。

2004 年、 Omer Reingoldによる画期的な論文により、USTCON は実際にLに属することが示されました。^[8]この論文では、入力グラフの検索を導くためにエクスパンダー グラフが使用されました。USTCON はSL完全であるため、Reingold の結果はSL = Lを意味し、 SLを別のクラスとして考えることの有用性を実質的に排除します。数週間後、大学院生の Vladimir Trifonov は、USTCON は空間を使用して決定論的に解くことができることを示し、これはより弱い結果ですが、異なる手法を使用しました。^[9] Reingold の USTCON アルゴリズムを実用的な定式化するための実質的な取り組みは行われていません。彼の論文 (およびそれに至る論文) では、主に漸近線に関心があることが明示されています。その結果、彼が説明するアルゴリズムは実際にはメモリと時間がかかります。つまり、 の場合でも、アルゴリズムには世界中のすべてのコンピューターに含まれるメモリ (1 キロエクサエクサエクサバイト) よりも多くのメモリが必要になります。 ${\displaystyle O{\text{(log }}n{\text{log log }}n)}$${\displaystyle 64^{32}\,\log N}$${\displaystyle O(N^{64^{32}})}$${\displaystyle N=2}$

LとSLの崩壊には、いくつかの重要な結果があります。最も明白なことは、すべてのSL完全問題がLに含まれるようになり、決定論的対数空間アルゴリズムと多重対数空間アルゴリズムの設計に有効に活用できることです。特に、対数空間削減に使用する新しいツール セットがあります。問題がLに含まれるのは、USTCON に対数空間削減可能である場合のみであることもわかっています。

• C. Papadimitriou .計算複雑性. Addison-Wesley, 1994. ISBN 0-201-53082-1​​ . 
• マイケル・シプサー著『計算理論入門』PWS Publishing Co.、ボストン、1997年ISBN 0-534-94728-X。