NL (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 NL은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다.
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에 따르면 다음 관계가 성립한다고 한다.
또한 NL=RL이라는 사실도 알려져 있다. RL은 확률적 튜링 기계가 로그 공간만 쓰고 시간 제약은 받지 않을 때 풀 수 있는 문제의 복잡도 종류로서, 예라고 답변해야 할 경우에 1/3보다 작은 확률로 아니오라고 잘못 답변할 가능성이 있다. 그리고 NL은 ZPL하고도 같다는 사실이 알려져 있다. ZPL은 확률적 알고리즘이 로그 공간만 쓰고 시간 제약은 받지 않을 때 잘못 없이 풀 수 있는 문제들의 복잡도 종류이다. 그러나 RL과 ZPL에 각각 다항 시간 제약을 준 복잡도 종류인 RLP나 ZPLP와 NL이 같은지는 알려져 있지 않다. 책에 따라서는 RLP와 RL, ZPLP와 ZPL을 섞어서 쓰기도 한다.
사비치 정리를 써서 NL과 결정론적 공간을 관련지을 수 있다. 사비치 정리에 따르면 어떤 비결정론적 알고리즘도 입력 크기에 대해 최대 2차 공간만 더 쓰면 결정론적 기계로 시뮬레이트할 수 있다. 또한 이라는 관계도 성립한다. 이는
과 같다. 이것은 1994년 현재까지 알려진 가장 강력한 결정론적 공간 포함관계이다. 더 큰 공간 복잡도 종류는 2차식에 따른 증가에 영향을 받지 않기 때문에 여기에 관련된 비결정론적 복잡도 종류와 결정론적 복잡도 종류는 같다고 알려져 있다. 이를테면 PSPACE = NPSPACE이다.
[편집] 확률적 정의
[편집] 서술 복잡도
NL을 논리적으로 특징화할 간단한 방법이 있다. NL은 추이 닫힘 연산자를 추가한 일차 논리로 표현할 수 있는 언어를 정확히 포함한다.
[편집] 참고문헌
- 크리스토스 파파디미트리우 (1994). “16: 로그 공간”, 《Computational Complexity》, 1판, Addison Wesley, 395-408. ISBN 0-201-53082-1.
- 마이클 사이프저 (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)이라 한 것이다.
주요 복잡도 종류 (더 보기) |
---|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |