오라클(신탁)

알고리즘이 계산 도중 어떤 문제 A 에 대한 질문을 던지면 곧바로 옳은 답을 돌려주는 가상의 장치다. 오라클 A 를 쓸 수 있는 다항 시간 알고리즘이 푸는 문제의 모임을 P^A, 비결정적인 경우를 NP^A 로 적는다. 실제 장치가 아니라 「A 를 공짜로 풀 수 있다면 무엇이 달라지는가」를 따지는 사고 도구이며, 문제 사이의 상대적 어려움을 재거나 증명 기법의 한계를 보이는 데 쓰인다.