SL(복잡성)

SL (complexity)

계산 복잡도 이론에서 SL(대칭 로그스페이스 또는 Sym-L)은 USTCON(비간접 s-t 연결)으로 환원 가능한 문제의 복잡도 등급으로, 비방향 그래프에서 두 정점 사이에 경로가 존재하는지 여부를 판단하는 문제로서, 그렇지 않으면 두 정점이 존재하는지 여부를 판단하는 문제로 설명된다.동일한 구성 요소에서이 문제는 또한 간접적인 도달 가능성 문제라고도 불린다.다원 환원성 또는 튜링 환원성을 사용하든 상관없다.비록 원래 대칭 튜링 기계의 관점에서 설명되었지만, 그러한 등가 공식은 매우 복잡하며, 환원성 정의는 실제로 사용되는 것이다.

USTCON은 STCON(방향 도달 가능성)의 특수한 경우로서, 지시된 그래프에서 두 꼭지점 사이에 지시된 경로가 존재하는지 여부를 판단하는 문제로서, NL에 대해서는 완료된다.USTCON은 SL-완전이기 때문에, USTCON에 영향을 미치는 대부분의 진전은 SL에도 영향을 미쳤다.따라서 그들은 서로 연결되어 있고, 함께 논의된다.

2004년 10월에 Omer Reingold는 SL = L을 보여주었다.

기원

SL은 1982년 해리 R에 의해 처음 정의되었다. USTCON을 배치할 클래스를 찾고 있던 루이스와 크리스토스 파파디미트리오우는 비결정주의를 요구하지 않는 듯함에도 불구하고 기껏해야 NL에만 배치할 수 있는 수업을 찾고 있었다.[1]그들은 대칭 튜링 기계를 정의하고, 그것을 사용하여 SL을 정의하고, SL에 대한 USTCON이 완성되었다는 것을 보여주었고, 그것을 증명했다.

여기서 L은 로그 공간의 일반적인 결정론적 튜링 기계에서 해결할 수 있는 더 잘 알려진 문제 등급이고, NL은 로그 공간의 비결정론적 튜링 기계에서 해결할 수 있는 문제 등급이다.후에 논의된 레인골드의 결과는 실제로 로그 공간에 제한되었을 때 대칭 튜링 기계는 결정론적 튜링 기계와 동력이 동일하다는 것을 보여준다.

완전한 문제

정의에 따르면, USTCON은 SL에 대해 완전하다(SL의 모든 문제는 SL 자체로 감소한다).USTCON에서 직간접적으로 줄임으로써 더 많은 흥미로운 완전한 문제들이 발견되었고, 그것들의 요약본은 알바레즈와 그린로우가 만들었다.[2]많은 문제들이 방향을 잡지 않은 그래프에 있는 그래프 이론 문제들이다.이들이 기술하는 가장 단순하고 중요한 SL-완전성 문제에는 다음이 포함된다.

  • 우스티콘
  • 대칭 튜링 기계의 시뮬레이션: STM은 단수로 주어진 특정 공간에 주어진 입력을 수용하는가?
  • 꼭지점 분리 경로: 두 꼭지점 사이에 k개의 경로가 있으며, 끝점에서만 정점을 공유하는가?(USTCON의 일반화, 그래프가 k 연결되었는지 여부를 묻는 것과 동등)
  • 주어진 그래프가 초당적인 그래프인가, 아니면 동등하게 2가지 색상을 사용한 그래프 색상이 있는가?
  • 두 개의 비방향 그래프가 동일한 수의 연결된 구성요소를 가지고 있는가?
  • 그래프에 짝수 수의 연결된 구성 요소가 있는가?
  • 그래프를 지정하면 주어진 에지를 포함하는 사이클이 있는가?
  • 두 그래프의 스패닝 포리스트가 동일한 수의 가장자리를 가지고 있는가?
  • 모든 가장자리의 무게가 구별되는 그래프를 볼 때, 주어진 가장자리는 최소 중량에 걸쳐 있는 포리스트에 있는가?
  • 배타적 또는 2-만족성: 또는 이(가) 여러 변수 쌍 i, ) 을 유지하도록 요구하는 공식이 주어질 경우 이 값을 참으로 만드는 변수에 할당이 있는가?

이 모든 문제의 보완점은 SL에도 있다. 우리가 보게 되겠지만 SL은 보완 하에 닫혀 있기 때문이다.

L = SL이라는 사실로부터, 로그 공간 감소와 관련하여 더 많은 문제가 SL-완전하다는 것을 따른다. L 또는 SL의 모든 비종속적인 문제는 SL-완전성이다. 더욱이 L-완전성은 L보다 더 작은 등급이라 하더라도 L-완전성은 SL-완전성에 해당한다.이런 의미에서 이 수업은 다소 하찮게 되었다.

중요한 결과

딥퍼스트 검색, 너비퍼스트 검색 등 잘 알려진 클래식 알고리즘이 있어 선형 시공간에서 USTCON을 해결한다.SL이 정의되기 훨씬 전에 나타난 그들의 존재는 SL이 P에 포함되어 있다는 것을 증명한다.또한 USTCON, 즉 SL이 NL에 있다는 것을 보여주는 것도 어렵지 않다. 왜냐하면 우리는 단지 어떤 정점이 존재하는지를 발견하기 위해 다음에 어떤 정점을 방문해야 하는지를 비결정론적으로 추측할 수 있기 때문이다.

그러나 SL의 첫 번째 비교 결과는 1970년에 증명된 Savitch의 정리였으며, 로그 n2 공간에서 USTCON을 해결하는 알고리즘을 제공하였다.그러나 깊이 우선 검색과 달리, 이 알고리즘은 잠재적으로 초항식 실행 시간 때문에 대부분의 애플리케이션에 비실용적이다.이것의 한 가지 결과는 USTCON, 즉 SL이 DSPACE(logn2)에 있다는 것이다.[3](사실 사비치의 정리는 NL이 DSPACE(logn2)에 있다는 더 강한 결과를 준다.)

사비치의 알고리즘에 22년 동안 (균일) 결정론적 공간 개선은 없었지만, 1979년 알레리우나스 외 연구진에 의해 매우 실용적인 확률론적 로그 공간 알고리즘이 발견되었는데, 그것은 단순히 한 꼭지점에서 시작해서 다른 꼭지점에서 찾을 때까지(그 후 수락) 또는V3 시간이 지날 때까지(그 후 거부) 무작위 산책을 수행하는 것이다.[4]거짓 거부는 무작위 보행이 오래 지속될수록 기하급수적으로 줄어들 수 있는 경계가 작은 확률로 이루어진다.이것은 SL이 다항 시간에서 해결 가능한 문제의 등급인 RLP에 포함되어 있고 시간의 1/3 미만으로 잘못 거부하는 확률적 기계와 로그 공간에 포함되어 있음을 보여주었다.Alliuanas 외 연구진은 또한 범용 횡단 순서에 의해 무작위 보행을 대체함으로써 L/poly에 SL이 포함되어 있다는 것을 보여주었다. L/poly는 다항식 조언으로 로그 공간에서 결정적으로 해결할 수 있는 문제의 불균일한 복잡성 등급이다.

1989년 보로딘 등은 두 정점이 서로 다른 연결 부품에 있는지 여부를 결정하는 USTCON의 보완도 RLP에 있음을 보여줌으로써 이 결과를 강화했다.[5]이로써 USTCON과 SL은 공동 RLP와 교차점에 배치되었고, ZPLP는 로그 공간이 있는 문제의 등급으로 예상 다항 시간, 오류 없는 무작위 알고리즘을 가진 문제의 등급인 ZPLP는 RLP와 공동 RLP의 교차점에 배치되었다.

1992년, 니산, 스제메레디, 위그더슨은 마침내1.5 로그 n 공간만을 사용하여 USTCON을 풀 수 있는 새로운 결정론적 알고리즘을 찾았다.[6]이것은 약간 개선되었지만, 레이놀드까지는 더 이상의 유의미한 이득은 없을 것이다.

1995년 니산과 타샤마는 SL이 보완하에 폐쇄된다는 놀라운 결과를 보여주었는데, 당시 많은 사람들이 SL = 공동 SL이라고 믿고 있었다.[7]마찬가지로 문제를 그래프로 줄이고 두 꼭지점이 같은 성분에 있는지 물어봄으로써 해결할 수 있다면 다른 그래프로 줄이고 두 꼭지점이 다른 성분에 있는지 물어봄으로써도 해결할 수 있다.그러나, Ringold의 논문은 나중에 이 결과를 중복되게 만들 것이다.

SL = co-SL의 가장 중요한 요소 중 하나는 LSL = SL; 즉 SL용 오라클을 가진 결정론적 로그 공간 기계는 SL의 문제를 해결할 수 있지만 다른 문제는 해결할 수 없다는 것이다.이것은 우리가 문제가 SL에 있다는 것을 보여주기 위해 튜링 환원성을 사용하든 아니면 다원 환원성을 사용하든 상관 없다는 것을 의미한다; 그것들은 동등하다.

2004년 10월 Omer Reingold의 획기적인 논문은 USTCON이 사실 L에 있다는 것을 보여주었다.[8] USTCON은 SL-complete이기 때문에, 이것은 SL = L을 의미하며, 기본적으로 SL을 별도의 등급으로 고려하는 것의 유용성을 제거한다.몇 주 후 대학원생 블라디미르 트리포노프는 USTCON이 log n O 공간을 다른 기법을 사용하여 결정적으로 해결될 수 있다는 것을 보여주었다.[9]레이놀드의 USTCON 알고리즘을 실용화하려는 노력은 많지 않았다.그의 논문(그리고 그것에 이르는 논문들)에 그들이 주로 점증요법에 관심이 있다는 것은 명백하다. 그 결과, 그가 기술한 알고리즘은 실제로 의 ^{32 N}와 O ( 즉 = 의 경우에도 알고리즘은 전 세계 모든 컴퓨터에 포함된 메모리보다 더 많은 메모리를 필요로 할 것이다(킬로엑세엑사바이트).

L = SL의 결과

L과 SL의 붕괴는 여러 중대한 결과를 초래한다.가장 명백하게 모든 SL-완전 문제는 현재 L에 있으며, 결정론적 로그 공간과 다변량 공간 알고리즘 설계에 유용하게 사용될 수 있다.특히 로그 공간 축소에 사용할 수 있는 새로운 툴이 있다.또한, USTCON으로 로그 공간을 축소할 수 있는 경우에만 문제가 L에 있다는 것이 현재 알려져 있다.

각주

  1. ^ 루이스, 해리 R.;Papadimitriou,인 크리스토 H.(1980년),"대칭 space-bounded 계산", 제7국제 콜로퀴움 자동자, 언어와 프로그래밍에, 강의 노트 컴퓨터 과학으로, 회보 85vol., 베를린:스프링거,를 대신하여 서명함. 374–384, doi:10.1007/3-540-10003-2_85, MR0589018.저널 버전 루이스, 해리 R.;Papadimitriou,인 크리스토 H.(1982년),"대칭 space-bounded 계산", 이론 컴퓨터 과학, 19(2):161–187, doi:10.1016(82)90058-5, MR0666539된다.
  2. ^ Àlvarez, Carme; Greenlaw, Raymond (2000), "A compendium of problems complete for symmetric logarithmic space", Computational Complexity, 9 (2): 123–145, doi:10.1007/PL00001603, MR 1809688.
  3. ^ Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences, 4: 177–192, doi:10.1016/S0022-0000(70)80006-X, hdl:10338.dmlcz/120475, MR 0266702.
  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. ^ Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzo, Walter L.; Tompa, Martin (1989), "Two applications of inductive counting for complementation problems", SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1.1.394.1662, doi:10.1137/0218038, MR 0996836.
  6. ^ Nisan, Noam; Szemerédi, Endre; Wigderson, Avi (1992), "Undirected connectivity in O(log1.5n) space", Proceedings of 33rd Annual Symposium on Foundations of Computer Science, pp. 24–29, doi:10.1109/SFCS.1992.267822.
  7. ^ Nisan, Noam; Ta-Shma, Amnon (1995), "Symmetric logspace is closed under complement", Chicago Journal of Theoretical Computer Science, Article 1, MR 1345937, ECCC TR94-003.
  8. ^ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014.
  9. ^ Trifonov, Vladimir (2008), "An O(log n log log n) space algorithm for undirected st-connectivity", SIAM Journal on Computing, 38 (2): 449–483, doi:10.1137/050642381, MR 2411031.

참조