1-3
PCP 정리
PCP theorem (probabilistically checkable proofs)
증명의 몇 군데만 무작위로 들춰 봐도 옳고 그름을 가릴 수 있다는 정리
NP 의 모든 문제에는, 검증자가 무작위로 고른 상수 개의 비트만 읽고도 옳은 증명은 언제나 받아들이고 거짓 명제의 증명은 높은 확률로 물리칠 수 있는 형식의 증명이 있다는 정리다. 1992년에 아로라·사프라, 그리고 아로라·룬드·모트와니·수단·세게디가 증명했다. 이 정리는 「근사해조차 구하기 어렵다」는 결과와 같은 말이다. 예를 들어 3-SAT 에서 충족되는 절의 비율을 어떤 상수 이상으로 보장하는 것만으로도 NP-난해다. NP 에 대한 이해가 깊어진 큰 성과이지만 P 와 NP 를 가르지는 못한다.