PCP 정리 — 증명을 몇 군데만 읽고 검사하기

PCP 정리는 NP 문제의 증거를 상수 개의 자리만 읽어도 확률적으로 검사할 수 있는 꼴로 다시 쓸 수 있다고 말한다(NP = PCP(log n, 1)). 이 정리는 「근사해를 구하는 것도 정확히 푸는 것만큼 어렵다」는 결과들과 같은 말이다.

중급
관리자
2026-10-05 23:05
조회 0
AI 도움

검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

PCP 정리는 NP 문제의 증거를 상수 개의 자리만 읽어도 확률적으로 검사할 수 있는 꼴로 다시 쓸 수 있다고 말한다. 이 글은 그 진술과 뜻, 이 정리가 「근사해를 구하는 것도 정확히 푸는 것만큼 어렵다」는 결과들과 같은 말이라는 점, 그리고 증명의 뿌리를 차례로 본다.

핵심 정리

PCP 정리: NP = PCP(log n, 1). NP 의 모든 언어에는 무작위 비트를 log n 의 상수 배만큼 쓰고 증명에서 상수 개의 비트만 읽는 검증자가 있다.
다시 쓴 증거에서는 오류가 한곳에 숨지 못하고 곳곳에 번진다. 그래서 몇 자리만 보아도 잘못된 증거는 절반 이상의 확률로 걸린다.
이 정리는 근사의 어려움과 같은 말이다. 충족 가능한 3SAT 식에서 절의 7/8 + ε 이상을 충족시키는 다항 시간 알고리즘이 있으면 P = NP 다(Håstad).
Arora 와 Safra, 그리고 Arora, Lund, Motwani, Sudan, Szegedy 가 1992년에 완성했고, Dinur 가 2005년에 훨씬 간단한 조합론적 증명을 내놓았다.
PCP 정리는 P ≠ NP 를 증명하지 않는다. 근사에 관한 결론은 모두 「그런 알고리즘이 있으면 P = NP」 꼴이다.

정확한 진술

PCP(r(n), q(n))

확률적으로 검사할 수 있는 증명(probabilistically checkable proof, PCP)의 검증자는 다항 시간에 도는 확률적 알고리즘이다. 입력 x 와 함께 증명 문자열 π 를 받는데, π 를 통째로 읽지 않고 원하는 자리만 골라 읽는다. 무작위 비트를 r(n) 개 쓰고 π 의 자리를 q(n) 개 읽는 검증자가 다음을 채우면, 언어 L 은 PCP(r(n), q(n)) 에 속한다고 한다(r 과 q 는 상수 배까지 허용한다).

완전성: x ∈ L 이면 검증자가 확률 1 로 받아들이는 증명 π 가 있다.
건전성: x ∉ L 이면 어떤 π 를 내밀어도 검증자가 받아들일 확률은 1/2 이하다.

PCP 정리 증명됨

NP = PCP(log n, 1).

Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy

곧 NP 의 모든 언어에는 무작위 비트를 log n 의 상수 배만큼 쓰고 증명에서 상수 개의 비트만 읽는 검증자가 있다. 반대 방향인 PCP(log n, 1) ⊆ NP 는 쉽다. 무작위 비트가 그 정도면 경우의 수가 다항식 개뿐이라 전부 해 볼 수 있다.

뜻

논리식이 충족 가능하다는 보통의 증거는 충족하는 대입이다. 이것을 확인하려면 증거 전체를 읽어야 한다. 한 군데만 틀려도 증거는 무효가 되는데, 그 한 군데가 어디인지 모르기 때문이다.

PCP 정리에 따르면 증거를 다른 형식으로 다시 쓸 수 있다. 다시 쓴 증거에서는 오류가 한곳에 숨지 못하고 곳곳에 번진다. 그래서 무작위로 고른 몇 자리만 보아도 잘못된 증거는 절반 이상의 확률로 걸린다. 검사를 c 번 되풀이하면 놓칠 확률은 2^(−c) 이하로 떨어진다. 옳은 증거는 언제나 통과한다. 수학의 형식 증명도 「길이 n 이하의 증명이 있는가」 꼴로 적으면 NP 문제이므로 같은 이야기가 그대로 적용된다.

두 줄로 된 그림. 윗줄은 보통의 증거(충족하는 대입)를 칸으로 늘어놓은 것으로, 잘못된 칸이 하나뿐이라 어디 있는지 모르면 전부 읽어야 한다고 적혀 있다. 아랫줄은 PCP 꼴로 다시 쓴 증거 π 로, 잘못된 칸이 곳곳에 퍼져 있다. 그 아래의 검증자가 log n 의 상수 배인 무작위 비트로 세 자리를 골라 화살표로 읽는다. 오른쪽에 잘못된 증거는 절반 이상의 확률로 걸리고 옳은 증거는 언제나 통과한다고 적혀 있다. — 보통의 증거에서는 오류가 한 칸에 숨지만, PCP 꼴로 다시 쓴 증거에서는 오류가 곳곳에 번져 몇 자리만 읽어도 걸린다. 칸 수와 오류 자리는 설명을 위한 보기다.

근사의 어려움과 같은 말이다

PCP 정리에는 겉보기에 전혀 다른 동치 형식이 있다.

PCP 정리의 동치 형식 증명됨

어떤 상수 q 와 ρ < 1 이 있어서, 변수 q 개씩에 걸린 제약들의 모임이 주어졌을 때 「모든 제약을 한꺼번에 채울 수 있는 경우」와 「어떤 대입으로도 ρ 비율까지만 채울 수 있는 경우」를 가려내는 일이 NP-난해다.

두 형식은 사전처럼 맞대응한다.

두 형식의 맞대응
검증자 형식	제약 형식
검증자	제약 모임
증명 π	변수의 대입
읽는 자리 수	제약 하나에 걸린 변수 수
건전성의 1/2	채울 수 있는 제약의 최대 비율

여기서 근사 알고리즘의 한계가 나온다.

MAX-3SAT 는 3SAT 식의 절을 되도록 많이 충족시키는 문제다. 어떤 상수 ρ < 1 이 있어서, 언제나 최적의 ρ 배 이상을 보장하는 다항 시간 알고리즘이 있으면 P = NP 다.
Håstad 는 이 문턱을 정확히 짚었다. 임의의 ε > 0 에 대해, 충족 가능한 3SAT 식을 받아 절의 7/8 + ε 이상을 충족시키는 대입을 내놓는 다항 시간 알고리즘이 있으면 P = NP 다. 한편 절마다 리터럴이 정확히 셋이면, 변수 값을 무작위로 정하기만 해도 평균적으로 절의 7/8 이 충족된다. 아무 생각 없이 얻는 7/8 과 NP-난해 사이에 틈이 없다.
최대 독립 집합이나 격자의 최단 벡터 문제에 대해서도 비슷한 결과가 뒤따랐다.

충족 가능한 3SAT 식에서 충족시키는 절의 비율을 0 부터 1 까지 수직선으로 그린 그림. 0 에서 7/8 까지는 회색 띠로, 절마다 리터럴이 정확히 셋이면 변수 값을 무작위로 정하기만 해도 평균 7/8 이 충족된다고 적혀 있다. 7/8 에서 1 까지는 자주색 띠로, 7/8 + ε 이상을 충족시키는 다항 시간 알고리즘이 있으면 P = NP 라고 적혀 있다. 두 띠가 맞닿는 7/8 에 틈이 없다는 표시가 있다. — Håstad 의 7/8 문턱. 아무 생각 없이 얻는 7/8 과 NP-난해한 구간이 딱 맞닿는다.

증명의 핵심 생각

뿌리는 대화형 증명 연구다. IP = PSPACE 와 그 뒤를 이은 다중 증명자 결과(Babai–Fortnow–Lund)를 NP 크기로 줄이는 작업이 이어졌고, Arora 와 Safra, 그리고 Arora, Lund, Motwani, Sudan, Szegedy 가 1992년에 정리를 완성했다. 학술지에는 1998년에 실렸다.

원래 증명은 대수적이다. 거칠게 말하면 증거를 낮은 차수의 다변수 다항식으로 부호화한다. 서로 다른 낮은 차수 다항식은 대부분의 점에서 값이 다르므로 오류가 한곳에 머물 수 없다. 검증자는 받은 것이 정말 그런 다항식인지를 표본 몇 개로 검사한다.
Dinur 는 2005년에 훨씬 간단한 조합론적 증명을 내놓았다. 제약 모임의 「채워지지 않는 비율」을, 모임의 크기는 상수 배만 키우면서 두 배로 늘리는 간격 증폭 보조정리가 핵심이다. 처음에는 아주 작던 간격이 이를 되풀이하는 동안 상수가 된다. 바탕 그래프가 확장 그래프(expander)라는 성질이 쓰인다.

이 정리와 그 응용에 2001년 괴델상이, Dinur 의 증명에 2019년 괴델상이 주어졌다.

P 대 NP 까지의 거리

그 대신 이 정리는 P 대 NP 문제의 무게를 넓혔다. P ≠ NP 이면 수많은 최적화 문제에서 정확한 해뿐 아니라 일정 수준 이상의 근사해도 다항 시간에 얻을 수 없다. Aaronson 은 여기서 P ≠ NP 를 믿을 근거도 읽어 낸다. 근사 비율을 조금씩 바꾸어 가면 문제가 P 에 속하는 구간과 NP-난해한 구간이 나오는데, 알려진 어떤 경우에도 두 구간은 겹치지 않는다. 7/8 처럼 딱 맞닿기도 하고 사이가 비어 있기도 하다. 한 번이라도 겹쳤다면 P = NP 가 되었을 것이다.

출처

Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 저자 공개 초고: https://theory.cs.princeton.edu/complexity/ (18장: 정의 18.1, 정리 18.2 와 주석, 따름정리 18.7, 정리 18.13 과 두 형식의 대응표, Cook–Levin 환산으로 부족한 까닭, 18.6절의 원래 증명 요약)
Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (3장: 정리 19 와 7/8 무작위 대입, 「보이지 않는 울타리」 논의)
S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, "Proof verification and the hardness of approximation problems", Journal of the ACM 45(3), 1998, 501–555. https://eccc.weizmann.ac.il/report/1998/008/
J. Håstad, "Some optimal inapproximability results", Journal of the ACM 48(4), 2001, 798–859. 저자 공개본: https://www.csc.kth.se/~johanh/optimalinap.pdf (초록)
I. Dinur, "The PCP theorem by gap amplification", Journal of the ACM 54(3), 2007, Article 12. ECCC TR05-046: https://eccc.weizmann.ac.il/report/2005/046/ (초록: 증폭 보조정리, 그래프 거듭제곱과 확장 그래프)
Wikipedia, "PCP theorem". https://en.wikipedia.org/wiki/PCP_theorem (보조 자료: 정리의 내력, 근사 불가능 결과의 예, 2001년·2019년 괴델상)
S. Arora, S. Safra, "Probabilistic checking of proofs: a new characterization of NP", Journal of the ACM 45(1), 1998, 70–122. https://doi.org/10.1145/273865.273901 (서지만 확인)

출처·이용 조건: 직접 작성

참고문헌 7

교과서원문 확인
Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009
계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.
확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
원문 주소 (theory.cs.princeton.edu)
개관원문 확인
P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음.
원문 주소 (www.scottaaronson.com)
부분 결과원문 확인
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)
부분 결과원문 확인
Some optimal inapproximability resultsJ. Håstad · 2001Journal of the ACM 48(4), 798–859쪽 (2001) · 학회 발표 STOC 1997, 1–10쪽
MAX-3SAT 을 비롯한 여러 문제에 대해 더는 좁힐 수 없는 근사 불가능성 문턱을 증명한 논문이다. 충족 가능한 3SAT 식에서 절의 7/8 보다 조금이라도 많은 비율을 늘 충족시키는 다항 시간 알고리즘이 있으면 P = NP 임을 보인다. 2-4 의 부분 결과 개관과 PCP 정리 글이 인용한다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 초록을 읽음.
원문 주소 (www.csc.kth.se)
부분 결과서지만 확인
The PCP theorem by gap amplificationI. Dinur · 2007Journal of the ACM 54(3), Article 12 (2007) · 학회 발표 STOC 2006, 241–250쪽 · ECCC TR05-046 (2005)
PCP 정리를 간격 증폭이라는 조합론적 방법으로 훨씬 간단하게 다시 증명한 논문이다. 제약 모임의 「채워지지 않는 비율」을 되풀이해 두 배로 늘리는 보조정리가 핵심이며, 확장 그래프의 성질이 쓰인다. 2-4 의 PCP 정리 글이 인용한다. ECCC 공개본으로 연결한다.
확인:ECCC TR05-046 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (eccc.weizmann.ac.il)
보조 자료원문 확인
PCP theoremWikipedia contributors · 2026영어 위키백과 (2026-10-05 확인)
PCP 정리를 다룬 영어 위키백과 문서다. 2-4 의 PCP 정리 글이 정리의 내력, 근사 불가능 결과의 예, 2001년·2019년 괴델상을 확인하는 보조 자료로 썼다.
확인:위키백과 문서를 직접 열어 해당 서술을 확인(2차 자료).
원문 주소 (en.wikipedia.org)
부분 결과서지만 확인
Probabilistic checking of proofs: a new characterization of NPSanjeev Arora, Shmuel Safra · 1998Journal of the ACM 45(1), 70–122쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 2–13쪽
NP 를 「무작위로 일부만 들춰 보는 증명」으로 새로 규정해 PCP 정리의 앞 절반을 놓은 논문이다. almss-1998 이 이 결과를 고쳐 읽는 비트 수를 상수로 줄였으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 18장으로 확인.
원문 주소 (doi.org)DOI 10.1145/273865.273901

하위 정보 0

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

아직 없습니다.