完全問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:34 UTC 版)
「SL (計算複雑性理論)」の記事における「完全問題」の解説
定義から、USTCON は明らかにSL-完全である（SLに属する問題は全てUSTCONに還元可能である）。USTCONに直接あるいは間接に還元することで様々な完全問題が見つかり、Àlvarez と Greenlaw がそれらをまとめた。その多くはグラフ理論における問題である。主なものを以下に列挙する。 USTCON 対称性チューリング機械のシミュレーション: 対称性チューリング機械にある領域を与えたとき、ある入力を受理するか? 点素な道（経路）: USTCON を経路長について一般化したもの 2部グラフかどうかの判定、またはグラフを2色でグラフ彩色できるか? 2つの無向グラフが同数の連結部分を持つか? グラフの連結部分が偶数個あるか? グラフの中のある枝について、それを含む輪があるか? 2つのグラフのスパニング木の枝数が同じか? グラフの各枝にそれぞれ異なる重み付けがされているとき、ある枝が最小重みスパニング森に含まれるか? 排他的論理和 2-充足可能性問題: 変項の対 (xi,xj) がいくつかあって、それらについて xi xor xj が成り立つ必要があるとき、全体が真となるような変項の値の組み合わせがあるか? これらの補問題もSLに属する。すなわち、SLは補問題について閉じている。 既に L = SL であることは分かっているので、対数領域還元によってさらに多数のSL-完全問題があることがわかっている。LまたはSLに属する問題は全てSL-完全であり、L-完全とSL-完全は等価である。そういった意味で複雑性クラスとしてはあまり重要ではなくなっている。
※この「完全問題」の解説は、「SL (計算複雑性理論)」の解説の一部です。
「完全問題」を含む「SL (計算複雑性理論)」の記事については、「SL (計算複雑性理論)」の概要を参照ください。
- 完全問題のページへのリンク
