부분 결과원문 확인
Proof verification and the hardness of approximation problemsSanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy · 1998Journal of the ACM 45(3), 501–555쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 14–23쪽NP 의 증명을 상수 개의 비트만 읽고 확률적으로 검증할 수 있음을 보여 PCP 정리를 완성한 논문이다. 그 귀결로, MAX-3SAT 같은 문제는 P ≠ NP 인 한 최적값에 얼마든지 가깝게 근사하는 다항 시간 방법을 가질 수 없음을 보인다. 근사 불가능성 이론의 원전을 찾는 독자에게 권한다. 공저자 Sudan 의 누리집에 있는 학술지판 공개본으로 연결한다.
확인:저자 공개본(학술지판)을 열어 초록을 읽음. 정리의 내용은 Arora–Barak 공개 초고 18장으로 확인.원문 주소 (people.csail.mit.edu)이 카드를 붙인 자료 4