L(복잡성)
L (complexity)계산 복잡성 이론에서 L(LSPACE 또는 DLOGSPACE라고도 함)은 쓰기 가능한 메모리 공간의 로그 양을 사용하여 결정론적 튜링 기계에 의해 해결될 수 있는 의사결정 문제를 포함하는 복잡성 등급이다.[1][2]형식적으로 튜링 기계에는 두 개의 테이프가 있는데, 그 중 하나는 입력을 암호화하고 읽기만 할 수 있는 반면, 다른 테이프는 로그 크기를 가지고 있지만 쓰기는 물론 읽기도 가능하다.로그 공간은 입력에[1] 일정한 수의 포인터와 로그 수의 부울 플래그를 보유하기에 충분하며, 많은 기본적인 로그 공간 알고리즘은 메모리를 이런 방식으로 사용한다.
완전한 문제 및 논리적 특성화
L의 모든 비경쟁적인 문제는 로그 공간 감소 하에서 완전하기 때문에 L-완전성의 의미 있는 개념을 식별하기 위해 더 약한 감소가 필요하며,[3] 가장 일반적인 것은 1차 감소가 된다.
Omer Reingold의 2004년 결과는 주어진 방향하지 않은 그래프에서 두 꼭지점 사이에 경로가 존재하는지의 문제인 USTCON이 L에 있다는 것을 보여주는데, 이는 USTCON이 SL-complete이기 때문에 L = SL임을 보여준다.[4]
이것의 한 가지 결과는 L의 단순한 논리적 특성이다. L은 추가된 상호 교환적 전이성 폐쇄 연산자와 함께 1차 로직에서 표현 가능한 언어들을 정확하게 포함한다(그래프 이론적 용어로, 이것은 연결된 모든 구성요소를 하나의 집단으로 변하게 한다.이 결과에는 데이터베이스 쿼리 언어에 대한 응용 프로그램이 있다. 쿼리의 데이터 복잡성은 데이터 크기를 변수 입력으로 간주하여 고정된 쿼리에 응답하는 복잡성으로 정의된다.이 조치의 경우, 관계 대수에서 표현된 것과 같은 완전한 정보(nulls 개념이 없음)를 가진 관계형 데이터베이스에 대한 질의는 L에 있다.
관련 복잡도 클래스
L은 NL의 하위 등급으로, 비계측 튜링 기계의 로그 공간에서 해독 가능한 언어의 등급이다.NL의 문제는 비결정론적 기계의 상태와 상태 전환을 나타내는 방향 그래프에서 도달성 문제로 변형될 수 있으며, 로그 공간 바운드는 이 그래프가 다항식 정점과 가장자리의 수를 가지며, 여기서부터 NL이 문제의 복잡성 등급 P에 포함됨을 의미한다.결정론적 다항식 시간에서 유효하다.[5]따라서 L ⊆ NL ⊆ P.또한 P에 L을 포함시키는 것은 더 직접적으로 증명될 수 있다: O(log n) 공간을 사용하는 디시더는 가능한 구성의 총 수이기 때문에 2O(log n) = n 시간O(1) 이상을 사용할 수 없다.
L은 다음과 같은 방식으로 클래스 NC와 추가로 관련이 있다: NC1 ⊆ L ⊆ NL ⊆ NC2.즉, 일부 상수 k에 대해 프로세서의 다항수 O(nk)를 가진 병렬 컴퓨터 C를 주어, O(log n) 시간에 C에서 해결할 수 있는 문제는 L에 있고, L의 모든 문제는 C의 O(log2 n) 시간에 해결할 수 있다.
중요한 개방 문제로는 L = P,[2] L = NL이 있다.[6]L = NP인지는 알 수조차 없다.[7]
기능 문제의 관련 등급은 FL이다.FL은 종종 로그 공간 축소를 정의하는데 사용된다.
추가 속성
L은 로그 공간에서 로그 공간 오라클 쿼리(거의 말하자면 "로그 공간을 사용하는 함수 호출")를 시뮬레이션할 수 있어 각 쿼리에 동일한 공간을 재사용할 수 있기 때문에 그 자체로 낮다.
기타 용도
로그스페이스의 주요 아이디어는 로그 공간에 다항식 숫자를 저장하고 입력 위치에 대한 포인터를 기억하는데 사용할 수 있다는 것이다.
따라서 로그 공간 클래스는 입력이 너무 커서 컴퓨터의 RAM에 맞지 않는 계산을 모델링하는 데 유용하다.긴 DNA 시퀀스와 데이터베이스는 주어진 시간에 입력의 일정한 부분만 RAM에 있고 검사할 입력의 다음 부분을 계산하는 포인터가 있는 문제의 좋은 예로서, 따라서 로그 메모리만 사용한다.
참고 항목
메모들
- ^ a b Sipser(1997), Definition 8.12, 페이지 295.
- ^ a b 개리 앤 존슨 (1979년), 177페이지.
- ^ Garey & Johnson(1979), Organization 7.13(청구 2), 페이지 179를 참조한다.
- ^ Reingold, Omer (2005). Undirected ST-connectivity in log-space. STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York. pp. 376–385. doi:10.1145/1060590.1060647. MR 2181639. ECCC TR04-094.
- ^ Sipser(1997), Corollary 8.21, 페이지 299.
- ^ Sipser(1997), 페이지 297, Garey & Johnson(1979), 페이지 180.
- ^ "Complexity theory - is it possible that $L=NP$?".
참조
- Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
- Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. Chapter 16: Logarithmic space, pp. 395–408. ISBN 0-201-53082-1.
- Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. Section 8.4: The Classes L and NL, pp. 294–296. ISBN 0-534-94728-X.
- Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Section 7.5: Logarithmic Space, pp. 177–181. ISBN 0-7167-1045-5.
- Cook, Stephen A.; McKenzie, Pierre (1987). "Problems Complete for Deterministic Logarithmic Space" (PDF). Journal of Algorithms. 8 (3): 385–394. doi:10.1016/0196-6774(87)90018-6. ISSN 0196-6774.
