장벽서지만 확인
Relativizations of the P =? NP QuestionTheodore Baker, John Gill, Robert Solovay · 1975SIAM Journal on Computing 4(4), 431–442쪽 (1975)P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 정리 3.9 와 Aaronson 2017 정리 43 으로 확인.