장벽서지만 확인
The random oracle hypothesis is falseRichard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi · 1994Journal of Computer and System Sciences 49(1), 24–39쪽 (1994)「무작위 오라클에 대해 확률 1 로 성립하는 진술은 오라클 없이도 참」이라는 무작위 오라클 가설이 거짓임을 보인 논문으로 널리 인용된다. 무작위 오라클에 대해서는 P ≠ NP 가 확률 1 로 성립한다는 결과(bennett-gill-1981)를 P ≠ NP 의 증거로 읽을 수 없는 까닭을 댈 때 인용한다. 반례는 IP 와 PSPACE 의 관계로 알려져 있다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자·권호·쪽을 확인했다(본문은 열지 못함).