L (복잡도)

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

계산 복잡도 이론에서 L은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. 로그 공간은 입력에 대한 포인터 상수개와 이진 플래그 로그 개를 담기에 충분하다는 것을 직관으로 알 수 있다.

L을 일반화한 것이 NL이다. NL은 비결정론적 튜링 기계가 로그 공간을 써서 판정할 수 있는 언어의 집합이다. 인 것은 자명하다. 그리고 O(log n) 공간을 쓰는 판정자는 시간을 아무리 많이 써도 가능한 경우의 수인 2^{O(log n)}=n^O(1)을 넘지 않는다. 따라서 가 된다. 여기서 P는 결정론적 다항 시간에 풀 수 있는 문제의 집합이다.

모든 L 문제는 로그 공간 환산에 대해 완전(complete)하다. 이 환산은 쓸모없기 때문에, L에 들어 있는 더 강한 완전 문제들을 동일시하는 더 약한 환산들이 정의되었다. 그러나 L-완전에 대한 정의 중 일반적으로 쓰이는 것은 없다.

아직 해결되지 않은 문제 중 중요한 것으로 L = P인가 하는 문제와 L = NL인가 하는 문제가 있다.

L과 관계 있는 문제로, 함수 문제에 대한 복잡도 종류인 FL이 있다. FL은 로그 공간 환산을 정의할 때 자주 쓰인다.

[편집] 참고문헌

• 크리스토스 파파드미트리오 (1994). “16: 로그 공간”, Computational Complexity, 1판 (in 영어), Addison Wesley, 395-408. ISBN 0-201-53082-1.
• ((영어)) Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
• 마이클 사이프저 (1997). “8.4 (복잡도 종류 L과 NL(The Classes L and NL))”, Introduction to the Theory of Computation (in 영어). PWS Publishing, 294-296. ISBN 0-534-94728-X.
• 마이클 게리, 데이비드 존슨 (1979). “7.5: 로그 공간”, Computers and Intractability: A Guide to the Theory of NP-Completeness (in 영어). W.H. Freeman, 177-181. ISBN 0-7167-1045-5.

주요 복잡도 종류 (더 보기)
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