NL (複雑さ)

コンピュータサイエンスにおける未解決の問題:

⁠ ⁠${\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}$

(コンピュータサイエンスにおける未解決の問題)

計算複雑性理論において、NL (非決定性対数空間) は、非決定性チューリング マシンが対数量のメモリ空間を使用して解決できる決定問題を含む複雑性クラスです。

NL は、決定性チューリングマシン上の対数空間問題のクラスであるLの一般化です。任意の決定性チューリングマシンは非決定性チューリングマシンでもあるため、LはNLに含まれます。

NL は、計算リソースの非決定性空間(または NSPACE)に関して、NL = NSPACE (log n ) として正式に定義できます。

複雑性理論における重要な結果により、この複雑性クラスを他のクラスと関連付けることができ、関連するリソースの相対的なパワーがわかります。一方、アルゴリズムの分野での結果は、このリソースでどの問題を解決できるかを教えてくれます。複雑性理論の多くの部分と同様に、 NLに関する多くの重要な疑問はまだ未解決です( 「コンピューター サイエンスにおける未解決の問題」を参照)。

NL は、以下の確率的定義によりRLと呼ばれることもありますが、この名前は、 NLと等しいかどうかが知られていないランダム対数空間を指すために使用されることが多いです。

ST 連結性や2 充足可能性など、いくつかの問題は対数空間削減の下でNL 完全であることが知られています。ST 連結性は、有向グラフ内のノードSとTについて、T がSから到達可能かどうかを尋ねます。2充足可能性は、各節が2 つのリテラルの選言である命題式が与えられた場合、式を真にする変数割り当てがあるかどうかを尋ねます。 が ではないことを示す例は次のようになります。 ${\displaystyle \neg}$

${\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}$

2-充足可能性に対する多項式時間アルゴリズムが存在するため、 NLがPに含まれることはわかっているが、NL = PかL = NLかはわかっていない。 NL = co-NLであることはわかっており、ここでco-NL は補語がNLに含まれる言語のクラスである。この結果 (イマーマン・シェレプチェニ定理) は、1987 年にニール・イマーマンとロバート・シェレプチェニによって独立に発見され 、この研究により 1995 年のゲーデル賞を受賞した。

回路の複雑さにおいて、NL はNC階層内に配置できます。Papadimitriou 1994 の定理 16.1 では、次のようになっています。

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$。

より正確には、NL はAC ¹に含まれます。NL は、対数空間と無制限の時間でランダム化アルゴリズムによってエラーなしで解ける問題のクラスであるZPLに等しいことが知られています。 ただし、 RLとZPLの多項式時間制限であるRLPまたはZPLPと等しいことは知られておらず、またそうであると考えられていません。一部の著者は、これらをRLとZPLと呼んでいます。

サビッチの定理を使ってNL を決定論的空間に関連付けることができます。この定理は、非決定論的アルゴリズムは、最大で 2 乗の空間で決定論的マシンによってシミュレートできることを示しています。サビッチの定理から、次のことが直接得られます。

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{同様に、}}{\mathsf {NL\subseteq L}}^{2}.}$

これは 1994 年に知られていた最も強力な決定論的空間包含でした (Papadimitriou 1994 問題 16.4.10、「対称空間」)。より大きな空間クラスは二次増加の影響を受けないため、非決定論的クラスと決定論的クラスは等しいことがわかっており、たとえばPSPACE = NPSPACEとなります。

C は、間違って受け入れることはないが、1/3 未満の確率で間違って拒否することが許される確率チューリングマシンを使用して対数空間で解決可能な決定問題の複雑性クラスであるとします。これは片側誤差と呼ばれます。定数 1/3 は任意です。0 ≤ x < 1/2 の任意のxで十分です。

C = NLであることがわかります。C は、その決定論的な対応物であるLとは異なり、多項式時間に制限されないことに注意してください。これは、多項式数の構成を持ちますが、ランダム性を使用して無限ループを回避できるためです。多項式時間に制限すると、クラスRLが得られます。これは、 NL に含まれますが、 NLと等しいとは知られていないか、または等しいとは考えられていません。

C = NLを証明する簡単なアルゴリズムがあります。明らかにC はNLに含まれます。

• 文字列が言語内にない場合、両方ともすべての計算パスで拒否されます。
• 文字列が言語内にある場合、NLアルゴリズムは少なくとも 1 つの計算パスに沿って受け入れ、Cアルゴリズムは少なくとも 3 分の 2 の計算パスに沿って受け入れます。

NLがCに含まれていることを示すには、NLアルゴリズムを使用して長さnのランダムな計算パスを選択し、これを 2 ⁿ回実行します。長さnを超える計算パスはなく、計算パスは全部で 2 ⁿ個あるため、受け入れ可能なパス (定数によって下方に制限される) にヒットする可能性が高くなります。

^{唯一の問題は、2 n}まで上がるバイナリ カウンターを log スペースに収める余裕がないことです。これを回避するには、ランダム カウンターに置き換えます。ランダムカウンターは、単にn 枚のコインを投げ、すべて表が出たら停止して拒否します。このイベントの確率は 2 ^{− n}なので、停止するまでに平均 2 ⁿステップかかると予想されます。連続して表が出た回数の合計を保持しておくだけでよく、これは log スペースでカウントできます。

Immerman-Szelepcsényi 定理によれば、NL は補集合に対して閉じているため、これらの確率計算における片側誤差はゼロ側誤差に置き換えることができます。つまり、これらの問題は、対数空間を使用し、決してエラーを起こさない確率チューリングマシンによって解くことができます。マシンが多項式時間のみを使用することを要求する、対応する複雑性クラスは ZPLP と呼ばれます。

したがって、空間だけを見ると、ランダム化と非決定論は同等に強力であるように思われます。

NL は、 NPなどのクラスと同様に、証明書によって同等に特徴付けることができます。追加の読み取り専用で一度だけ読み取り可能な入力テープを持つ、決定論的な対数空間で制限されたチューリングマシンを考えてみましょう。言語がNLに属する場合、そのようなチューリングマシンは、追加の入力テープ内の適切な証明書の選択に対して言語内の任意の単語を受け入れ、証明書に関係なく言語にない任意の単語を拒否します。^[1]

Cem SayとAbuzer Yakaryılmazは、上記の文の決定論的対数空間チューリングマシンは、定数個のランダムビットのみを使用できる、誤差制限のある確率的定数空間チューリングマシンに置き換えることができることを証明しました。^[2]

NLには単純な論理的特徴があります。NL には、推移閉包演算子を追加した一階述語論理で表現できる言語が正確に含まれています。

クラス NL は、補集合、和集合、したがって積集合、連結、およびクリーネスター演算に対して閉じています。

• 複雑動物園: NL
• Papadimitriou, C. (1994)。「第 16 章: 対数空間」。計算複雑性。Addison- Wesley。ISBN 0-201-53082-1。
• Michael Sipser (1997 年 6 月 27 日)。「セクション 8.4 ～ 8.6: クラス L と NL、NL 完全性、NL は coNL に等しい」。計算理論入門。PWS 出版。294 ～ 302 ページ。ISBN 0-534-94728-X。
• 複雑性理論入門: 講義 7。Oded Goldreich。命題 6.1。C は、Goldreichが badRSPACE(log n) と呼ぶものです。