L (복잡도)
계산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. 로그 공간은 입력에 대한 포인터 상수개와 이진 플래그 로그 개를 담기에 충분하다는 것을 직관으로 알 수 있다.
L을 일반화한 것이 NL이다. NL은 비결정론적 튜링 기계가 로그 공간을 써서 판정할 수 있는 언어의 집합이다. L ⊆ NL인 것은 자명하다. 그리고 O(log n) 공간을 쓰는 판정자는 시간을 아무리 많이 써도 가능한 경우의 수인 2O(log n)=nO(1)을 넘지 않는다. 따라서 L ⊆ P가 된다. 여기서 P는 결정론적 다항 시간에 풀 수 있는 문제의 집합이다.
모든 L 문제는 로그 공간 환산에 대해 완전(complete)하다. 이 환산은 쓸모없기 때문에, L에 들어 있는 더 강한 완전 문제들을 동일시하는 더 약한 환산들이 정의되었다. 그러나 L-완전에 대한 정의 중 일반적으로 쓰이는 것은 없다.
아직 해결되지 않은 문제 중 중요한 것으로 L = P인가 하는 문제와 L = NL인가 하는 문제가 있다.
L과 관계 있는 문제로, 함수 문제에 대한 복잡도 종류인 FL이 있다. FL은 로그 공간 환산을 정의할 때 자주 쓰인다.
2004년 10월에 오메르 레인골드가 발표한 획기적인 논문에 따르면, 주어진 무향 그래프의 두 꼭짓점 사이에 길이 있는가 하는 문제인 USTCON은 L이다. 이 결과는 L = SL라는 것을 뜻한다. USTCON은 SL-완전이기 때문이다.
이 결과로 L의 논리적 특징이 하나 도출된다. L은 1차 술어 논리에 교환 가능한 이행적 폐쇄 연산자를 덧붙여 표현할 수 있는 언어의 집합과 똑같다는 것이다.
L 자신은 low이다. 로그 공간 신탁 질의(대강 말해서, 로그 공간을 쓰는 함수 호출)를 로그 공간만 써서 시뮬레이트할 수 있기 때문이다. 이때 로그 공간만 쓰기 위해서 질의마다 같은 공간을 재활용한다.
참고 문헌[편집]
- 크리스토스 파파디미트리우 (1994). 〈16: 로그 공간〉. 《Computational Complexity》 (영어) 1판. 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》 (영어). PWS Publishing. 294-296쪽. ISBN 0-534-94728-X.
- 마이클 게리, 데이비드 S. 존슨 (1979). 〈7.5: 로그 공간〉. 《Computers and Intractability: A Guide to the Theory of NP-Completeness》 (영어). W.H. Freeman. 177-181쪽. ISBN 0-7167-1045-5.