NL (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 NL은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다.
NL은 결정론적 튜링 기계에서 로그 공간을 들여 푸는 문제의 집합인 L을 일반화한 것이다. 모든 결정론적 튜링 기계는 비결정론적 튜링 기계이기도 하기 때문에, L은 NL에 들어간다.
NL은 계산 자원인 비결정론적 공간(곧 NSPACE)이라는 개념을 사용해서 NL = NSPACE(log n)이라고 공식적으로 정의할 수 있다.
목차 |
[편집] NL-완전 문제
[편집] 확률적 정의
[편집] 서술 복잡도
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 (in 영어). 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 |
