NL (복잡도)

계산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다.

NL은 결정론적 튜링 기계에서 로그 공간을 들여 풀 수 있는 문제의 집합인 L을 일반화한 것이다. 모든 결정론적 튜링 기계는 비결정론적 튜링 기계이기도 하기 때문에, L은 NL에 들어간다.

NL의 공식적인 정의는 비결정론적 공간(곧 NSPACE)이라는 계산 자원 개념을 사용해서 한다. 이에 따르면 NL = NSPACE(log n)이다.

NL은 아래 나오는 확률적 정의 때문에 RL이라고도 한다. 그러나 RL은 RLP를 나타내는 데 주로 쓰인다.

NL-완전 문제

복잡도 종류에서 가장 "어려운" 문제가 그 종류 이름에 완전이 붙는 문제들이다. 완전 문제를 빠르게 푸는 방법이 있다면, 그 복잡도 종류의 문제들은 그 방법으로 빠르게 풀 수 있다.

NL-완전이라고 알려진 문제로는 ST-연결성 문제와 2-만족성 문제가 있다. ST-연결성(또는 도달가능성) 문제는 유향 그래프에서 꼭짓점 S와 T를 연결하는 경로가 있는지를 결정하는 문제이다. 2-만족성 문제는 모든 절이 두 리터럴의 논리합인 논리식이 있을 때, 이 식을 만족하도록 진리값을 할당할 수 있는지를 묻는 문제이다.

포함 관계

NL은 P에 포함된다는 사실이 알려져 있다. 2-만족성 문제를 푸는 다항 시간 알고리즘이 있기 때문이다. 그러나 NL = P인지 아닌지 L = NL인지 아닌지는 알려져 있지 않다. 비결정론적 공간은 보수(complement)에 대해 닫혀 있기 때문에 NL = co-NL이다.

회로 복잡도에서 NL은 NC 위계에 놓일 수 있다. 크리스토스 파파디미트리우가 지은 《계산 복잡도》에 나오는 정리 16.1에 따르면 다음 관계가 성립한다고 한다.

$\mathbf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}$

또한 NL=RL이라는 사실도 알려져 있다. RL은 확률적 튜링 기계가 로그 공간만 쓰고 시간 제약은 받지 않을 때 풀 수 있는 문제의 복잡도 종류로서, 예라고 답변해야 할 경우에 1/3보다 작은 확률로 아니오라고 잘못 답변할 가능성이 있다. 그리고 NL은 ZPL하고도 같다는 사실이 알려져 있다. ZPL은 확률적 알고리즘이 로그 공간만 쓰고 시간 제약은 받지 않을 때 잘못 없이 풀 수 있는 문제들의 복잡도 종류이다. 그러나 RL과 ZPL에 각각 다항 시간 제약을 준 복잡도 종류인 RLP나 ZPLP와 NL이 같은지는 알려져 있지 않다. 책에 따라서는 RLP와 RL, ZPLP와 ZPL을 섞어서 쓰기도 한다.

사비치 정리를 써서 NL과 결정론적 공간을 관련지을 수 있다. 사비치 정리에 따르면 어떤 비결정론적 알고리즘도 입력 크기에 대해 최대 2차 공간만 더 쓰면 결정론적 기계로 시뮬레이트할 수 있다. 또한 $\mathbf {NL\subseteq SPACE} (\log ^{2}n)$이라는 관계도 성립한다. 이는 $\mathbf {NL\subseteq L} ^{2}$과 같다. 이것은 1994년 현재까지 알려진 가장 강력한 결정론적 공간 포함관계이다. 더 큰 공간 복잡도 종류는 2차식에 따른 증가에 영향을 받지 않기 때문에 여기에 관련된 비결정론적 복잡도 종류와 결정론적 복잡도 종류는 같다고 알려져 있다. 이를테면 PSPACE = NPSPACE이다.

확률적 정의

복잡도 종류 C가 확률적 튜링 기계로 로그 공간을 들여서 풀 수 있는 문제로서, 절대로 잘못 승인하는 일은 없지만, 1/3보다 낮은 확률로 잘못 거부할 수는 있는 문제라고 하자. 여기서 상수 1/3은 임의로 정해진 수치이다. 0 ≤ x < 1/2 범위에 있는 어떤 x라도 상관 없다.

그러면 C는 NL이다. 이와 대응하는 판정 복잡도 종류인 L과 달리, C는 다항 시간이라는 제약이 없다. 난수성을 이용해 무한 반복에서 빠져나올 수 있기 때문이다. 만약 여기에 다항 시간 제약이 있다면, 다른 복잡도 종류인 RLP가 된다. (NL과 RLP가 서로 다른 복잡도 종류인지는 아직 확실치 않다. 이는 P-NP 문제와 관련이 있다.)

C가 NL과 같다는 것을 보이는 간단한 알고리즘이 있다. 먼저, C가 NL에 속하는 것은 틀림없다. 이유는 아래와 같다.

• 입력 문자열이 언어에 속하지 않으면, 모든 계산 경로를 거부한다
• 입력 문자열이 언어에 속하면, NL 알고리즘은 최소한 한 계산 경로를 승인한다. 그리고 C 알고리즘은 적어도 전체 계산 경로 중 2/3 이상을 승인한다.

NL이 C에 속한다는 것을 보이기 위해서, NL 알고리즘을 취하고 길이가 n인 랜덤 계산 경로를 선택한다. 그리고 이것을 2ⁿ 번 반복한다. 길이가 n을 넘는 계산 경로는 없고 계산 경로가 모두 2ⁿ개 있기 때문에, 그중 하나를 승인할 가능성이 높아진다. (일정한 상수 이하로)

여기서 유일한 문제는 2ⁿ까지 올라가는 이진 계수기는 로그 공간으로 부족하다는 점이다. 이 문제를 해결하기 위해 임의화된 계수기를 사용한다. 이 계수기는 단순히 동전 n개를 동시에 뒤집고 모든 동전이 앞면을 위로 향했을 때 멈추고 거부한다. 이 사건은 2^-n 확률로 일어나기 때문에 과정이 멈추기까지 평균 2ⁿ 시행이 필요할 것으로 예상할 수 있다. 이 계수기에서는 앞면이 위로 향한 개수만 세면 되고, 이것은 로그 공간으로도 할 수 있다.

따라서 공간만 고려하는 관점에서는 랜덤화와 비결정성은 동등하게 강력한 것으로 보인다.

서술 복잡도

NL을 논리적으로 특징화할 간단한 방법이 있다. NL은 추이 닫힘 연산자를 추가한 일차 논리로 표현할 수 있는 언어를 정확히 포함한다.

참고 문헌

• 크리스토스 파파디미트리우 (1994). 〈16: 로그 공간〉. 《Computational Complexity》 1판. Addison Wesley. 395-408쪽. ISBN 0-201-53082-1.  CS1 관리 - 추가 문구 (링크)
• 마이클 사이프저 (1997). 〈8.4-8.6(복잡도 종류 L과 NL, NL-완전, NL은 coNL과 같다)〉. 《Introduction to the Theory of Computation》 (영어). PWS Publishing. 294-302쪽. ISBN 0-534-94728-X. 
• (영어) Introduction to Complexity Theory: Lecture 7. Oded Goldreich. 명제 6.1. 여기서 C는 골트라이히가 badRSPACE(log n)이라 한 것이다.