단어	복잡도
단어	L
설명	계산 복잡도 이론에서 L(복잡도)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. 로그 공간은 입력에 대한 포인터 상수 개와 이진 플래그 로그 개를 담기에 충분하다는 것을 직관으로 알 수 있다. L을 일반화한 것이 NL이다. NL은 비결정론적 튜링 기계가 로그 공간을 써서 판정할 수 있는 언어의 집합이다. 인 것은 자명하다. 그리고 O(log n) 공간을 쓰는 판정자는 시간을 아무리 많이 써도 가능한 경우의 수인 2O(log n)=nO(1)을 넘지 않는다. 따라서 가 된다. 여기서 P는 결정론적 다항 시간에 풀 수 있는 문제의 집합이다.