NL (복잡도) 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''NL'''(Nondeterministic Logarithmic-space)은 [[비결정론적 튜링 기계]]가 [[로그]] [[기억 공간]]을 써서 풀 수 있는 [[판정 문제]]의 [[복잡도 종류]]이다.

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

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

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

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

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

==포함 관계==

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

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

:<math>\mathbf{NC_1 \subseteq L \subseteq NL \subseteq NC_2}</math>

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

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

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

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

C가 NL과 같다는 것을 보이는 간단한 알고리즘이 있다. 먼저, C가 '''NL'''에 속하는 것은 틀림없다. 이유는 아래와 같다.
* 입력 문자열이 언어에 속하지 않으면, 모든 계산 경로를 거부한다
* 입력 문자열이 언어에 속하면, NL 알고리즘은 최소한 한 계산 경로를 승인한다. 그리고 C 알고리즘은 적어도 전체 계산 경로 중 2/3 이상을 승인한다.
NL이 C에 속한다는 것을 보이기 위해서, NL 알고리즘을 취하고 길이가 n인 랜덤 계산 경로를 선택한다. 그리고 이것을 2<sup>n</sup> 번 반복한다. 길이가 n을 넘는 계산 경로는 없고 계산 경로가 모두 2<sup>n</sup>개 있기 때문에, 그중 하나를 승인할 가능성이 높아진다. (일정한 상수 이하로)

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

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

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

== 참고 문헌 ==
* {{서적 인용|저자 = [[크리스토스 파파디미트리우]] | 연도 = 1994 | 제목 = Computational Complexity |url = https://archive.org/details/computationalcom0000papa | 출판사 = Addison Wesley | 판 = 1판 |ISBN=0-201-53082-1| 장 = 16: 로그 공간 | 페이지 = [https://archive.org/details/computationalcom0000papa/page/395 395]-408}}
* {{서적 인용|저자 = [[마이클 사이프저]] | 연도 = 1997 | 제목= Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | 출판사 = PWS Publishing | 언어= 영어 |ISBN=0-534-94728-X| 장= 8.4-8.6(복잡도 종류 L과 NL, NL-완전, NL은 coNL과 같다) | 페이지 = [https://archive.org/details/introductiontoth00sips/page/294 294]-302}}
* {{언어링크|en}} [https://web.archive.org/web/20160303183247/http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps Introduction to Complexity Theory: Lecture 7]. Oded Goldreich. 명제 6.1. 여기서 ''C''는 골트라이히가 badRSPACE(log n)이라 한 것이다.

{{복잡도 종류}}

[[분류:복잡도 종류]]