원전서지만 확인
Computational Complexity of Probabilistic Turing MachinesJohn Gill · 1977SIAM Journal on Computing 6(4), 675–695쪽 (1977) · 학회 발표 STOC 1974 (Proceedings of the 6th Annual ACM Symposium on Theory of Computing), 91–95쪽동전을 던지는 튜링 기계를 정의하고, 확률적 다항 시간에 인식되는 언어 클래스들을 정해 NP 와 견준 논문이다. BPP·RP·PP·ZPP 같은 확률적 클래스의 출전으로 인용된다. 「무작위성을 쓰면 NP 문제가 쉬워지는가」를 다루는 글이 정의의 근거로 삼는다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.