重要な成果

ウィキペディア小見出し辞書

重要な成果

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:34 UTC 版)

「SL (計算複雑性理論)」の記事における「重要な成果」の解説

深さ優先探索や幅優先探索といった古典的アルゴリズムは、USTCONを線形時間と線形領域で解くことができる。これらはSLが定義されるずっと以前からあり、SLがPに属することを証明している。USTCON（すなわちSL）はNLに属することも容易に示すことができる。 SLに関する自明でない成果は、1970年に証明されたサヴィッチの定理である。これにより、USTCON を log2 n 領域で解くアルゴリズムがもたらされた。しかし、深さ優先探索とは異なり、このアルゴリズムは時間に関しては多項式時間以上の時間がかかることがあり、実用的ではない。この結果から、USTCON およびSLは DSPACE(log2n) に属することが示された。実際にはサヴィッチの定理はもっと広範囲なもので、NLが DSPACE(log2n) に属することを示した。 決定性領域については、サヴィッチの定理以後22年間進歩が見られなかったが、1979年、Aleliunas らはUSTCONの実用的な確率的対数領域アルゴリズムを発見した。これは1つの頂点からランダムウォークし、|V|3 回過ぎても解に到達しないときに受理しないとするアルゴリズムである。誤って拒絶する確率は小さく、ランダムウォークを継続するほど指数関数的にその確率が減少していく。これにより、SLはRLPに属することが示された。RLPとは、確率的チューリング機械で多項式時間と対数領域で解くことができ、誤って拒絶する確率は1/3未満とされる複雑性クラスである。 1989年、Borodin らはこの結果を出発点として、USTCONの補問題（2つの頂点が別の連結部分に属するか）もRLPに属することを示した。これにより、USTCONおよびSLは co-RLP にも属することになり、RLP と co-RLP の交差である ZPLP に属することが明らかとなった。ZPLP は、対数領域でかつ多項式時間が期待されるラスベガス法で解ける問題のクラスである。 1992年、Nisan、Szemerédi、Wigderson は USTCON を log1.5 n の領域で解ける決定性の新たなアルゴリズムを発見した。その後、若干の改良が加えられている。 1995年、Nisan と Ta-Shma は、SL が補問題について閉じていること（すなわち SL = co-SL）を示した。当時、SL と co-SL は異なると考えられていた。 SL = co-SL の重要な系の1つとして、LSL = SL がある。すなわち、決定性の対数領域を持つチューリング機械にSLの神託機械を付加すると、SLに属する問題は明らかに解けるが、それ以外の問題は解けない。これは、ある問題がSLに属することを示すのに、チューリング還元でも多対一還元でもよいということを示している。 2004年10月、Omer Reigngold は USTCON が実際には Lに属することを示した。USTCON は SL-完全とされていたため、この事実によって SL = L であることが判明した。数週間後、Vladimir Trifonov は USTCON を O(log n log log n) 領域で解く決定性のアルゴリズムを示した。