RL(복잡도)

RL (complexity)

RLP([1]랜덤화 로그 공간 다항식 시간)[2]라고도 불리는 RL(랜덤화 로그 공간 다항식 시간)은 로그 공간과 다항식 시간에서 단측 오류가 있는 확률론적 튜링 기계로 해결할 수 있는 계산 복잡도 이론 문제의 복잡도 클래스입니다.이것은 RP와 비슷하지만 로그 공간 제한이 없는 것과 비슷합니다.

정의.

RL의 정의에서 확률론적 튜링 기계는 결코 잘못 수용하지 않지만 1/3 미만의 시간에서 잘못 거부하도록 허용된다. 이것은 단측 오차라고 불린다.상수 1/3은 임의이며 0 < x < 1이면 됩니다.이 오차는 알고리즘을 반복 실행함으로써 다항식 시간이나 로그 공간 이상을 사용하지 않고 모든 다항식 p(x)에 대해 2배 작게−p(x) 만들 수 있습니다.

다른 복잡도 클래스와의 관계

때로는 RL이라는 이름이 로그 공간 확률론적 기계로 해결할 수 있는 문제의 클래스를 위해 제한된다.단, 이 클래스는 확률론적 카운터를 사용하여 NL과 동일한 것으로 나타낼 수 있으며, 이는 RL이 NL에 포함되어 있음을 나타냅니다. 또한 RL은 유사하지만 양면 오류를 허용하는 BPL에 포함되어 있습니다(잘못된 수용).RL은 로그 공간에서 결정론적 튜링 기계에 의해 해결될 수 있는 문제인 L을 포함하고 있는데, 그 정의는 단지 더 일반적이기 때문이다.

노암 니산은 1992년에 RL이 결정론적 튜링 기계에서 다항식 시간과 다항식 공간에서 풀 수 있는 문제 클래스인 [3]SC에 포함되어 있다는 약한 탈란수 결과를 보여주었다. 다시 말해, 다항식 공간이 주어지면, 결정론적 기계는 로그 공간 확률론적 알고리즘을 시뮬레이션할 수 있다.

RL은 L과 같다고 믿는다. 즉, 다항식 시간 로그 공간 계산은 완전히 탈난도화될 수 있다.[4] 이에 대한 주요 증거는 2005년 라인골드 등에 의해 제시되었다.이것의 증거는 복잡계급의 무조건적인 탈란도화 분야에서 노력의 성배이다.SL이 L과 동등하다는 Omer Reingold의 증명은 중요한 진전이었다.

레퍼런스

  1. ^ 복잡성 동물원: RL
  2. ^ A. 보로딘, S.A. 쿡, P.W. 다이몬드, W.L. 루조, M.Tompa. 보완 문제에 대한 유도 계수의 두 가지 적용.SIAM Journal on Computing, 18(3): 559 ~578 . 1989.
  3. ^ 를 클릭합니다Nisan, Noam (1992), "RL ⊆ SC", Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92), Victoria, British Columbia, Canada, pp. 619–623, doi:10.1145/129712.129772.
  4. ^ O. 라인골드와 L. 트레비산과 S.바단의사랜덤은 이중규격 그래프와 RL vs. L 문제, ECCC TR05-022, 2004로 이동합니다.