L/폴리

L/poly

계산 복잡성 이론에서 L/poly는 다항식 조언이 있는 로그 공간 기계의 복잡도 등급이다.L/[1]poly는 균일하지 않은 다항 시간 클래스 P/poly와 유사하게 균일하지 않은 로그 공간 클래스다.

형식적인 언어 L이 L/poly에 속하려면, n의 길이 다항식 문자열에 정수 n을 매핑하는 조언 함수가 있어야 하며, 입력 크기에 2개의 읽기 전용 입력 테이프와 크기 로그의 읽기-쓰기 테이프 1개가 있는 튜링 머신 M이 있어야 하며, 입력 크기에는 길이 n의 입력 x가 L에 속할 경우에만 해당된다.입력 x, f(n)[2]대안으로 보다 간단하게 L은 다항식 크기의 분기 프로그램을 통해 인지할 수 있는 경우에만 L/poly로 되어 있다.[3]이 두 가지 연산 모델이 동급이라는 증거의 한 방향은 다항식 크기의 분기 프로그램이 존재할 경우 자문 함수에 의해 지정되고 튜링 기계에 의해 시뮬레이션될 수 있다는 관측이다.다른 방향에서 로그 쓰기 가능 공간과 다항식 조언 테이프가 있는 튜링 기계는 쓰기 가능 테이프의 구성과 다른 두 테이프에서 튜링 기계 헤드의 위치를 나타내는 상태를 나타내는 분기 프로그램을 통해 시뮬레이션할 수 있다.

1979년 알레리우나스 외 연구진은 대칭 로그 공간이 L/폴리 안에 포함되어 있다는 것을 보여주었다.[4]그러나 이 결과는 SL이 균일한 로그공간으로 붕괴된다는 오메르 린골드의 결과로 대체되었다.[5]

BPL은 애들만의 정리 변종인 L/poly에 포함되어 있다.[6]

참조

  1. ^ 복잡성 동물원: L/폴리.
  2. ^ Thierauf, Thomas (2000), The Computational Complexity of Equivalence and Isomorphism Problems, Lecture Notes in Computer Science, vol. 1852, Springer-Verlag, p. 66, ISBN 978-3-540-41032-4.
  3. ^ Cobham, Alan (1966), "The recognition problem for the set of perfect squares", Proceedings of the 7th Annual IEEE Symposium on Switching and Automata Theory (SWAT 1966), pp. 78–87, doi:10.1109/SWAT.1966.30.
  4. ^ Aleliunas, Romas; Karp, Richard M.; Lipton, Richard J.; Lovász, László; Rackoff, Charles (1979), "Random walks, universal traversal sequences, and the complexity of maze problems", Proceedings of 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, pp. 218–223, doi:10.1109/SFCS.1979.34, MR 0598110.
  5. ^ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014.
  6. ^ Nisan, Noam (1993), "On read-once vs. multiple access to randomness in logspace", Theoretical Computer Science, 107 (1): 135–144, doi:10.1016/0304-3975(93)90258-U, MR 1201169.


P ≟ NP

이 이론적인 컴퓨터 과학 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.