SC(복잡성)

SC (complexity)

계산 복잡성 이론에서 SC(Steve's Class, Stephen Cook의 이름을 따서 명명)[1]는 다항 시간(클래스 P)과 다항식 공간(클래스 PolyL)에서 결정론적 튜링 기계로 해결할 수 있는 문제의 복잡성 등급이다(일부 상수 k에 대한 O(log n)k 공간).DTISP(폴리, 폴리로그)라고도 할 수 있는데, 여기서 DTISP는 결정론적 시공간을 의미한다.SC의 정의는 P ∩ PolyL과 다르다는 점에 유의하십시오. 전자의 경우 다항 시간 및 다항 시간 공간 모두에서 단일 알고리즘이 실행되어야 하는 반면 후자의 경우 두 개의 개별 알고리즘으로 충분할 것이다. 즉, 다항 시간에서 실행되는 알고리즘과 다항 시간 공간에서 실행되는 알고리즘이다.(SC와 P ∩ PolyL이 등가인지는 알 수 없다.)

결정론적 푸시다운 오토마타에 의해 인식된 문맥 없는 언어의 엄격한 하위 집합체인 DCFL은 1979년 쿡이 보여주듯이 SC에 포함되어 있다.[2]P ∩ PolyL로 알려져 있지만, 모든 맥락 없는 언어가 SC에서 인식될 수 있다면 개방되어 있는가?[3]

P ∩ PolyL(DFS 알고리즘과 Savitch의 정리 때문에)에 있는 것으로 알려져 있지만 지시된 st-연결성이 SC에 있으면 개방된다.이 문제는 NL ⊆ SC에 해당한다.

RL과 BPL은 로그 공간과 다항식 시간에서 확률론적 튜링 기계가 수용할 수 있는 문제의 종류다.노암 니산은 1992년 SC에 둘 다 들어 있는 약한 비완도화 결과를 보여주었다.[4]즉, 다변성 공간이 주어진 경우 결정론적 기계는 로그 공간 확률론적 알고리즘을 시뮬레이션할 수 있다.

참조

  1. ^ 복잡성 동물원: SC
  2. ^ S. A. 요리사.결정론적 CFL은 다항 시간과 로그 제곱 공간에서 동시에 허용된다.ACM STOC'79, 페이지 338–345. 1979.
  3. ^ TCS 스택 교환: o(n^2) 공간을 사용한 CFG 구문 분석
  4. ^ 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.
P ≟ NP

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