상대화

어떤 증명이 관련된 모든 기계에 임의의 오라클을 똑같이 붙여도 성립하면 그 증명은 상대화된다고 한다. 기계를 블랙박스처럼 흉내 내기만 하는 논증, 곧 대각선 논법과 모의는 모두 상대화된다. 베이커·길·솔로베이는 1975년에 P^A = NP^A 가 되는 오라클 A 와 P^B ≠ NP^B 가 되는 오라클 B 가 둘 다 있음을 보였다. 따라서 상대화되는 기법만으로는 P = NP 도 P ≠ NP 도 증명할 수 없다. P 대 NP 를 풀려면 계산의 내부 구조를 들여다보는 기법이 있어야 한다는 뜻이다.