NL (計算複雑性理論)
ある複雑性クラスに属する最も難しい問題を指して完全問題という。直観的には、完全問題を効率的に解く方法が判っていれば、それを使ってそのクラスのあらゆる問題を解くことが出来る。すなわち、完全問題はその複雑性クラスの能力の程度を示すものである。
NL完全であることが判っている問題はいくつかある。STCON問題(有向グラフの2点間の経路の有無を問う問題)と2元充足可能性問題はNL完全である。2元充足可能性問題とは、連言標準形の論理式の各節(論理和で表される部分)が2つの変数で構成されているとき、その論理式を真とする変数値の組み合わせが存在するかどうかを問う問題である。以下にそのような論理式の例を示す。なお、~(チルダ)は「否定」を意味する。
(x1 or ~x3) and (~x2 or x3) and (~x1 or ~x2)