L (복잡도)
1. 개요
L은 결정적 로그 공간에서 해결 가능한 문제의 복잡도 클래스이다. L의 모든 비자명 문제는 로그 공간 환산에 대해 완전하며, 1차 논리 환산이 L-완전성을 식별하는 데 사용된다. L은 SL과 같으며, 1차 논리에 가환 추이적 폐포 연산자를 추가하여 표현할 수 있는 언어를 포함한다. L은 NL의 하위 클래스이고, P에 포함되며, NC 클래스와도 관련이 있다. L = P, L = NL, L = NP인지는 컴퓨터 과학의 미해결 문제로 남아 있다. 관련 클래스의 함수 문제는 FL이며, L은 자체적으로 낮다. 로그 공간은 대규모 계산을 모델링하는 데 유용하며, 긴 DNA 서열 및 데이터베이스와 같은 문제에 적용된다.
2. 완전 문제와 논리적 특성화
오메르 레잉골드의 2004년 연구 결과에 따르면, 주어진 무향 그래프에서 두 정점 사이에 경로가 존재하는지 여부를 묻는 문제인 USTCON이 L에 속한다. USTCON이 SL-완전하므로, 이는 L = SL임을 의미한다.
3. 관련 복잡도 종류
L은 NL의 하위 클래스이며, NL은 비결정적 튜링 기계에서 로그 공간으로 결정 가능한 언어의 클래스이다. NL의 문제는 비결정적 기계의 상태와 상태 전이를 나타내는 방향 그래프에서 도달 가능성 문제로 변환될 수 있으며, 로그 공간 경계는 이 그래프가 다항식 개수의 정점과 간선을 갖는다는 것을 의미한다. 이로부터 NL이 결정적 다항 시간 내에 해결 가능한 문제의 복잡도 클래스인 P에 포함된다는 결론이 나온다. 따라서 L ⊆ NL ⊆ P 이다. L이 P에 포함되는 것은 더 직접적으로 증명될 수도 있는데, O(log n) 공간을 사용하는 결정기는 2O(log n) = nO(1) 시간 이상을 사용할 수 없다. 이는 가능한 전체 구성의 수이기 때문이다.
L은 NC 클래스와도 관련이 있다.
NC1 ⊆ L ⊆ NL ⊆ NC2.
다시 말해, 어떤 상수 k에 대해 다항식 개수 O(nk)의 프로세서를 가진 병렬 컴퓨터 C가 주어지면, O(log n) 시간에 C에서 해결될 수 있는 모든 문제는 L에 속하고, L의 모든 문제는 C에서 O(log2 n) 시간에 해결될 수 있다.
중요한 미해결 문제에는 L = P인지, L = NL인지가 포함된다. 심지어 L = NP인지도 알려져 있지 않다.
관련된 클래스의 함수 문제는 FL이다. FL은 종종 로그 공간 감소를 정의하는 데 사용된다.