대화형 증명(IP)

계산 능력에 제한이 없지만 믿을 수 없는 증명자와, 무작위를 쓰는 다항 시간 검증자가 메시지를 주고받는 증명 방식이다. 참인 명제는 검증자를 높은 확률로 설득할 수 있어야 하고, 거짓인 명제는 증명자가 어떻게 속이려 해도 높은 확률로 들통나야 한다. 이렇게 증명할 수 있는 문제의 모임이 IP 다. 적힌 증거를 읽기만 하는 NP 의 검증에 대화와 무작위를 더한 것인데, 놀랍게도 IP = PSPACE 임이 밝혀졌다(샤미르, 1990년 발표). 이 증명과 그 바탕이 된 Lund·Fortnow·Karloff·Nisan 의 결과는 산술화를 써서 상대화 장벽을 넘은 대표 사례다.