세 장벽 한눈에 보기 — 왜 그 길로는 안 되는가
장벽이란 어떤 부류의 증명 기법으로는 P vs NP 를 풀 수 없음을 보인 정리다. 상대화·자연 증명·대수화 세 장벽을 한 표로 정리하고, 새 증명 아이디어를 볼 때 「이 장벽을 어떻게 넘는가」를 먼저 묻는 이유를 설명한다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
상대화·자연 증명·대수화, 세 장벽은 「이러저러한 성질을 가진 증명 기법으로는 P vs NP 를 해결할 수 없다」는 것을 수학적으로 증명한 정리들이다. 이 글은 세 장벽을 한 표로 정리하고, 새 증명 아이디어를 볼 때 「이 장벽을 어떻게 넘는가」를 먼저 묻는 이유를 설명한다.
장벽이란 무엇인가
P vs NP 를 풀려는 시도는 여러 번 「거의 다 왔다」는 기대를 낳았다가 멈췄다. 그때마다 연구자들은 한 걸음 물러서서 물었다. 지금까지 써 온 기법들에 공통된 성질이 있는가? 그 성질을 가진 기법으로 이 문제를 풀 수 있기는 한가?
- 장벽(barrier)
- 이 물음에 「없다」고 답하는 정리다. 곧 「이러저러한 성질을 가진 증명 기법으로는 P vs NP 를 해결할 수 없다」는 것을 수학적으로 증명한 결과다.
Aaronson 과 Wigderson 은 이것을 문제에 대한 발견이 아니라 기법에 대한 「메타 발견(meta-discovery)」이라 불렀다.
세 장벽
| 상대화(relativization) | 자연 증명(natural proofs) | 대수화(algebrization) | |
|---|---|---|---|
| 언제, 누가 | 1975년, Baker·Gill·Solovay | 1994년 발표, Razborov·Rudich | 2008년 발표, Aaronson·Wigderson |
| 겨냥한 기법 | 대각선 논법처럼 기계를 블랙박스로 다루는 논증 | 1980년대의 조합적 회로 하한 논증 | 산술화(논리식을 다항식으로 바꾸는 기법)와 대각선 논법의 결합 |
| 그 기법들의 공통 성질 | 모든 기계에 같은 오라클을 달아 주어도 논증이 그대로 통한다 | 「어려운 함수」를 가려내는 데 쓰는 성질이 계산하기 쉽고(구성성), 무작위 함수 가운데 무시할 수 없는 비율이 그 성질을 가진다(큼) | 오라클을 유한체 위의 저차 다항식으로 확장해 주어도 논증이 그대로 통한다 |
| 정리의 내용 | PA = NPA 인 오라클 A 와 PB ≠ NPB 인 오라클 B 가 모두 있다 | 충분히 강한 유사난수 생성기가 있다면, 그런 성질로는 일반 회로에 대한 초다항 하한을 증명할 수 없다 | 대수적 오라클을 기준으로 해도 P 와 NP 가 같아지는 세계와 달라지는 세계가 모두 있다 |
| 뜻 | 상대화하는 논증으로는 P = NP 도 P ≠ NP 도 증명할 수 없다 | 그런 하한 증명은 암호를 깨는 알고리즘을 덤으로 내놓게 된다 | 산술화를 더해도 P vs NP 나 NEXP ⊄ P/poly 는 증명할 수 없다 |
| 가정 | 없음 | 강한 유사난수 생성기의 존재 | 없음 |
| 피해 간 예 | IP = PSPACE, AC⁰ 회로 하한 | 대각선 논법(「큼」을 쓰지 않는다) | NEXP ⊄ ACC⁰ |
세 장벽은 서로 다른 쪽을 막는다
세 장벽은 한 줄로 늘어서 있지 않다. Aaronson 의 정리를 따르면 이렇다.
- 대각선 논법 같은 논리적 기법은 자연 증명에는 걸리지 않지만 상대화에 걸린다.
- 무작위 제한법 같은 조합적 기법은 상대화에는 걸리지 않지만 자연 증명에 걸린다.
- 둘을 섞은 산술화 기반 기법은 두 장벽을 함께 피해 MAEXP ⊄ P/poly 같은 회로 하한을 얻었지만, 대수화에 걸린다.
그래서 P ≠ NP 의 증명은 세 장벽을 동시에 피해야 한다. 지금까지 셋을 모두 피한 것으로 평가되는 회로 하한은 Williams 의 NEXP ⊄ ACC⁰ 다. Aaronson 의 2017년 개관에 따르면, 이 「알고리즘에서 하한으로」 접근과 기하적 복잡도 이론에는 아직 형식적인 장벽이 알려져 있지 않다.
왜 「이 장벽을 어떻게 넘는가」를 먼저 묻는가
새 증명 아이디어를 볼 때 연구자들은 세부 계산을 따라가기 전에 이 질문부터 던진다. 이유는 셋이다.
- 싸고 강한 검사다. 논증 어디에도 오라클 앞에서 깨지는 단계가 없다면, 수백 쪽을 다 읽지 않아도 그 논증이 틀렸거나 불완전함을 알 수 있다. Baker–Gill–Solovay 정리에 어긋나기 때문이다. Razborov 와 Rudich 도 논문에서, 어떤 접근이 상대화한다는 이유로 제외되듯 「자연화」한다는 이유로도 제외될 수 있다고 썼다.
- 실제로 그렇게 쓰인다. 2010년 Deolalikar 의 P ≠ NP 원고가 공개되었을 때, Lipton 은 첫 소개 글에서 곧바로 상대화 문제를 걱정거리로 꼽았고, 원고가 Baker–Gill–Solovay 와 Razborov–Rudich 의 장벽을 다루는지부터 살폈다.
- 아이디어를 다듬는 길잡이다. 장벽은 증명이 계산의 어떤 성질을 써야 하는지 알려 준다. 오라클이 없는 실제 계산에만 있는 성질, 무작위 함수에는 없고 NP-완전 문제에는 있는 성질이 그것이다.
주의할 점
출처
- T. Baker, J. Gill, R. Solovay, "Relativizations of the P =? NP Question", SIAM J. Comput. 4(4), 431–442 (1975). 서지는 DOI 등록 정보로, 정리의 진술은 Aaronson 2017 §6.1.2 로 확인.
- A. A. Razborov, S. Rudich, "Natural Proofs", J. Comput. System Sci. 55(1), 24–35 (1997). 저자 공개본에서 정의(§2)와 정리 4.1, 「자연화」에 관한 문장을 확인.
- S. Aaronson, A. Wigderson, "Algebrization: A New Barrier in Complexity Theory", ACM Trans. Comput. Theory 1(1) (2009). 저자 공개본 §1 에서 「meta-discoveries」라는 표현과 결과 목록을 확인.
- S. Aaronson, "P =? NP", 저자 공개본(2017). §4(P 에 속한 문제에 대한 검사), §6(기법과 장벽의 대응, 장벽이 알려지지 않은 접근), §6.4.2(NEXP ⊄ ACC⁰ 와 장벽)를 확인.
- M. Sipser, "The History and Status of the P versus NP Question", STOC 1992, 603–618. §3.1 을 확인.
- R. Williams, "Nonuniform ACC Circuit Lower Bounds", J. ACM 61(1), 1–32 (2014). 저자 공개본의 초록을 확인.
- R. J. Lipton, "A Proof That P Is Not Equal To NP?", 블로그 Gödel's Lost Letter and P=NP, 2010년 8월 8일.
출처·이용 조건: 직접 작성
참고문헌 7
- 장벽서지만 확인Relativizations of the P =? NP QuestionTheodore Baker, John Gill, Robert Solovay · 1975SIAM Journal on Computing 4(4), 431–442쪽 (1975)
P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 정리 3.9 와 Aaronson 2017 정리 43 으로 확인. - 장벽원문 확인Natural proofsAlexander A. Razborov, Steven Rudich · 1997Journal of Computer and System Sciences 55(1), 24–35쪽 (1997) · 학회 발표 STOC 1994 (Proceedings of the 26th Annual ACM Symposium on Theory of Computing), 204–213쪽
알려진 회로 하한 증명들의 공통된 꼴을 「자연 증명」으로 정식화하고 그 한계를 보인 논문이다. 어려움에 관한 가정(강한 유사난수 생성기의 존재)이 참이라면 자연 증명으로는 일반 회로에 대한 초다항 하한을 증명할 수 없다는 둘째 장벽의 원전이다. 회로 하한 연구가 왜 막혔는지 이해하려는 독자에게 권한다. 게시자(Elsevier) 페이지로 연결된다.
확인:저자 공개본을 열어 §2(정의), §3.1, §4(정리 4.1·4.3)를 읽음. 연결한 게시자 주소의 서지는 DOI 등록 기록으로 확인. - 장벽원문 확인Algebrization: A New Barrier in Complexity TheoryScott Aaronson, Avi Wigderson · 2009ACM Transactions on Computation Theory 1(1), 1–54쪽 (2009) · 학회 발표 STOC 2008 (Proceedings of the 40th Annual ACM Symposium on Theory of Computing), 731–740쪽
상대화를 넘어선 산술화 기법에도 한계가 있음을 보인, 대수화 장벽의 원전이다. 초록과 서론이 상대화·자연 증명·대수화 세 장벽의 관계를 정리하고 있어 2-2 를 깊이 읽으려는 독자의 다음 단계로 알맞다. 본론은 전문 연구자용이다. Aaronson 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 초록, §1, 정의 2.1–2.3 을 읽음. - 개관원문 확인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년 판)을 열어 인용한 절들을 읽음. - 개관원문 확인The history and status of the P versus NP questionMichael Sipser · 1992STOC 1992 (Proceedings of the 24th Annual ACM Symposium on Theory of Computing), 603–618쪽
P 대 NP 문제의 뿌리와 1992년까지의 연구 상황을 정리한 개관 논문이다. 문제의 의의와 역사, 대각선 논법과 회로 복잡도(얕은 회로·단조 회로)로 이어진 시도들을 차례로 설명한다. 부록에는 괴델이 폰 노이만에게 보낸 편지 전문의 영문 번역이 실려 있다. 30여 년 전 글이지만 큰 그림을 잡으려는 입문·중급 독자에게 여전히 좋다. ACM 디지털 도서관으로 연결된다.
확인:공개 사본으로 본문과 부록(괴델 편지의 영문 번역 포함)을 읽음. 연결한 ACM 디지털 도서관 주소의 서지는 DOI 등록 기록으로 확인. - 부분 결과원문 확인Nonuniform ACC Circuit Lower BoundsRyan Williams · 2014Journal of the ACM 61(1), 1–32쪽 (2014) · 학회 발표 CCC 2011 (26th Annual IEEE Conference on Computational Complexity), 115–125쪽
NEXP 의 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. 회로의 충족 가능성을 전수 조사보다 조금이라도 빨리 푸는 알고리즘을 만들면 회로 하한이 따라 나온다는 연결을 써서, 알고리즘 설계로 하한을 증명했다. 알려진 장벽들을 피한 드문 사례로 꼽힌다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본(2012-07-31 판)을 열어 초록, 서론, 정리 1.1·1.2 를 읽음. - 증명 주장원문 확인A Proof That P Is Not Equal To NP?R. J. Lipton · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 8일
Deolalikar 의 P ≠ NP 원고를 처음 소개한 Lipton 의 블로그 글이다. 원고를 진지한 연구자가 쓴 논문으로 소개하면서 논증의 뼈대를 요약하고, 상대화 문제를 걱정거리로 꼽는다. 2-5 의 Deolalikar 사례 글, 2-1 의 연표, 2-2 의 장벽 개관이 인용한다.
확인:블로그 글을 직접 열어 읽음.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.