폴리엘

계산 복잡성 이론에서 polyL은 입력 크기에서 다변량 함수에 의해 공간 복잡성이 경계가 되는 알고리즘에 의해 결정론적 튜링 기계에서 해결될 수 있는 의사결정 문제의 복잡도 등급이다.즉, polyL = DSPACE((log n)),^O(1) 여기서 n은 입력 크기를, O(1)는 상수를 나타낸다.

L ⊆ P, polyL ⊆ QP와 같이.그러나 polyL과 p의 유일한 입증된 관계는 polyL ≠ P이다. polyL ⊊ P, p ⊊ polyL, 또는 둘 중 어느 것도 다른 polyL에 포함되어 있지 않은지는 알 수 없다.polyL ≠ P에 대한 한 가지 증거는 p가 로그 공간 하의 완전한 문제를 가지고 있다는 것이다 - 다수를 감소시키지만 polyL은 공간 계층 구조 정리 때문에 발생하지 않는다.공간 계층 구조 정리는 모든 정수 d > 0에 대해 DSPACE(log^d n) ⊊ DSPACE(log^{d + 1} n) guarantees DSPACE(log n)를 보장한다. polyL이 완전한 문제를 가지고 있다면, 그것을 A라고 부른다. 문제 B가 DSPACE^{k + 1}(log^k n) \ Dspace(log^k n)의 요소라고 가정한다.A가 완료되었다는 가정은 B에 대한 다음과 같은 O(log^k n) 공간 알고리즘을 내포하고 있다: 로그 공간에서 B를 A로 줄인 다음 O(log^k n) 공간에서 A를 결정한다.이는 B가 DSPACE(log^k n)의 요소여서 공간 계층구성에 위배된다는 것을 암시한다.

외부 링크

• 복잡성 동물원: polyL