L (복잡도)

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

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

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

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

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

2004년 10월에 오메르 레인골드가 발표한 획기적인 논문에 따르면, 주어진 무향 그래프의 두 꼭짓점 사이에 길이 있는가 하는 문제인 USTCON은 L이다. 이 결과는 L = SL라는 것을 뜻한다. USTCON은 SL-완전이기 때문이다.

이 결과로 L의 논리적 특징이 하나 도출된다. L은 1차 술어 논리에 교환 가능한 이행적 폐쇄 연산자를 덧붙여 표현할 수 있는 언어의 집합과 똑같다는 것이다.

L 자신은 low이다. 로그 공간 신탁 질의(대강 말해서, 로그 공간을 쓰는 함수 호출)를 로그 공간만 써서 시뮬레이트할 수 있기 때문이다. 이때 로그 공간만 쓰기 위해서 질의마다 같은 공간을 재활용한다.

참고 문헌 
 
  Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.
 
 

복잡도 종류