검증자와 증거

검증자는 입력 x 와 증거 w 를 받아 w 가 「x 의 답은 예」를 뒷받침하는지 다항 시간에 확인하는 알고리즘이다. 증거(certificate, witness)는 해밀턴 경로 문제라면 경로 자체, SAT 라면 식을 참으로 만드는 변수 값이다. NP 는 「예인 입력에는 검증자를 통과하는 다항 길이의 증거가 있고, 아니오인 입력에는 어떤 증거도 통과하지 못하는」 문제의 모임으로 정의된다. 검증자는 증거를 어떻게 찾았는지는 묻지 않는다. 찾기와 확인하기의 차이가 P 대 NP 문제의 핵심이다.