부분 결과서지만 확인
Interactive proofs and the hardness of approximating cliquesUriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy · 1996Journal of the ACM 43(2), 268–292쪽 (1996) · 학회 발표 FOCS 1991 (32nd Annual Symposium on Foundations of Computer Science), 2–12쪽 — 학회판 제목은 「Approximating clique is almost NP-complete」그래프의 최대 클릭 크기를 근사하는 일과 증명자 여럿인 대화형 증명 사이의 연결을 처음 세운 논문이다. 「근사해도 어렵다」는 결과를 증명 검사 이론에서 끌어내는 방법의 출발점이며, 이듬해의 PCP 정리(arora-safra-1998, almss-1998)로 이어진다. 근사 알고리즘의 한계를 P ≠ NP 가정에서 끌어내는 글에 필요하다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.