2-2
세 장벽
상대화 · 자연 증명 · 대수화 — 어떤 증명 기법이 왜 통하지 않는가.
- 세 장벽 한눈에 보기 — 왜 그 길로는 안 되는가
장벽이란 어떤 부류의 증명 기법으로는 P vs NP 를 풀 수 없음을 보인 정리다. 상대화·자연 증명·대수화 세 장벽을 한 표로 정리하고, 새 증명 아이디어를 볼 때 「이 장벽을 어떻게 넘는가」를 먼저 묻는 이유를 설명한다.
- 상대화 장벽 — 대각선 논법만으로는 안 되는 이유
Baker–Gill–Solovay 정리(1975)는 P^A = NP^A 인 오라클 A 와 P^B ≠ NP^B 인 오라클 B 가 모두 있음을 보였다. 그래서 오라클을 달아도 그대로 통하는 논증으로는 P vs NP 를 어느 쪽으로도 증명할 수 없다.
- 자연 증명 장벽 — 하한 증명이 암호를 깨뜨린다
Razborov 와 Rudich 는 1980년대의 회로 하한 증명들이 구성성과 큼이라는 두 조건을 만족함을 보이고, 강한 유사난수 생성기가 있다면 그런 「자연 증명」으로는 일반 회로에 대한 초다항 하한을 얻을 수 없음을 증명했다.
- 대수화 장벽 — 산술화로도 넘지 못하는 선
산술화는 상대화 장벽을 넘었고, 대각선 논법과 결합해 자연 증명 장벽까지 피하는 회로 하한을 낳았다. Aaronson 과 Wigderson 은 오라클에 저차 다항식 확장을 붙여 주어도 통하는 논증으로는 P vs NP 나 NEXP ⊄ P/poly 를 증명할 수 없음을 보였다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.