산술화

x ∧ y 를 x·y 로, ¬x 를 1 − x 로 바꾸는 식으로 논리식을 유한체 위의 다항식으로 옮기는 기법이다. 그러면 0 과 1 뿐 아니라 다른 값에서도 식을 계산해 볼 수 있고, 차수가 낮은 서로 다른 두 다항식은 대부분의 점에서 값이 다르다는 성질로 오류를 잡아낼 수 있다. 1990년 무렵 대화형 증명의 결과들(IP = PSPACE 등)과 PCP 정리가 이 기법에서 나왔다. 계산을 블랙박스로 다루지 않으므로 상대화되지 않는 기법의 대표 사례이지만, 대수화 장벽은 넘지 못한다.