부분 결과서지만 확인
Two theorems on random polynomial timeLeonard Adleman · 1978FOCS 1978 (19th Annual Symposium on Foundations of Computer Science), 75–83쪽무작위 다항 시간에 풀리는 문제는 다항 크기 회로로도 풀린다는 결과의 출전으로 널리 인용된다. 무작위성은 입력 길이마다 주어지는 조언 문자열로 바꿀 수 있다는 논법의 원형이다. NP 가 다항 크기 회로를 갖지 않음을 보이면 무작위 알고리즘으로도 NP-완전 문제를 못 푼다는 설명에 쓰인다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자·학회·쪽을 확인했다(본문은 열지 못함).