Loading article…
コンピュータサイエンスにおいて、st-連結性またはSTCONは、有向グラフの頂点sとtについて、 tがsから到達可能かどうかを問う決定問題です。
形式的には、決定問題は次のように与えられる。
逐次コンピュータでは、st-連結性は深さ優先探索または幅優先探索のいずれかによって線形時間で容易に解くことができます。計算複雑性におけるこの問題への関心は、より限定された形式の計算に対するその複雑性に関係しています。たとえば、対数量のメモリのみを使用する非決定性チューリングマシンで解くことができる問題の複雑性クラスはNLと呼ばれます。st-連結性問題はNLに属することが示せます。非決定性チューリングマシンはパスの次のノードを推測でき、保存する必要がある情報はパスの全長と現在考慮中のノードだけだからです。アルゴリズムは、目標ノードtに到達するか、これまでのパスの長さがグラフのノード数nを超えた場合に終了します。
st連結性の補集合であるst非連結性も、 Immerman–Szelepcsényiの定理 によりNL = coNLであるため、クラスNLに属します。
特に、st-連結性の問題は実際にはNL完全であり、つまり、NLクラスのすべての問題は、対数空間還元の下で連結性に還元できます。これは、より強い場合である1次還元でも真です（Immerman 1999 、p. 51）。NLの任意の言語からSTCONへの対数空間還元は、次のように進みます。NLの言語を受け入れる非決定性対数空間チューリングマシンMを考えます。作業テープには対数空間しかないため、チューリングマシンのすべての可能な状態（ここで、状態とは、内部有限状態マシンの状態、ヘッドの位置、および作業テープの内容）は多項式個です。決定性対数空間マシンのすべての可能な状態をグラフの頂点にマッピングし、非決定性マシンの1ステップ以内にuから状態vに到達できる場合は、uとvの間にエッジを配置します。機械が受け入れるかどうかという問題は、開始状態から受け入れ状態への経路が存在するかどうかという問題と同じである。
サビッチの定理は、アルゴリズムがO (log 2 n )の決定論的空間でシミュレートできることを保証する。
無向グラフの場合の同じ問題は無向st連結性と呼ばれ、 Omer ReingoldによってLに属することが示されました。この研究により、彼は2005年のGrace Murray Hopper賞を受賞しました。無向st連結性は以前からクラスSLに対して完全であることが知られていたため、Reingoldの研究はSLがLと同じクラスであることを示しました。交代グラフの場合、この問題はP完全です（Immerman 1999 、p. 54）。