NL (복잡도)

위키백과 ― 우리 모두의 백과사전.

계산 복잡도 이론에서 NL비결정론적 튜링 기계로그 기억 공간을 써서 풀 수 있는 판정 문제복잡도 종류이다.

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

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

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

목차

[편집] NL-완전 문제

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

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

[편집] 포함 관계

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

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

\mathsf{NC_1 \subseteq L \subseteq NL \subseteq NC_2}

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

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

[편집] 확률적 정의

[편집] 서술 복잡도

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

[편집] 참고문헌


주요 복잡도 종류 (더 보기)

P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C
EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH