HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-2 세 장벽

상대화 장벽 — 대각선 논법만으로는 안 되는 이유

Baker–Gill–Solovay 정리(1975)는 P^A = NP^A 인 오라클 A 와 P^B ≠ NP^B 인 오라클 B 가 모두 있음을 보였다. 그래서 오라클을 달아도 그대로 통하는 논증으로는 P vs NP 를 어느 쪽으로도 증명할 수 없다.

  • 중급
  • 관리자
  • 조회 0
  • AI 도움
검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

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

오라클을 달아도 그대로 통하는 논증으로는 P vs NP 를 어느 쪽으로도 증명할 수 없다. 이 글은 그 근거인 Baker–Gill–Solovay 정리(1975)와, 이 장벽을 넘은 상대화하지 않는 결과 IP = PSPACE 를 살펴본다.

오라클과 상대화

오라클(oracle)
어떤 언어 O 에 대해 「이 문자열이 O 에 속하는가?」라는 질문에 한 단계 만에 답해 주는 가상의 장치다.

오라클에 물을 수 있는 튜링 기계로 정의한 P 와 NP 를 PO, NPO 라 쓴다. O 가 쉬운 언어면 달라지는 것이 없고, 어려운 언어면 기계가 그만큼 강해진다.

왼쪽의 오라클 기계 M 이 오른쪽의 오라클 O 에 「문자열 w 가 O 에 속하는가?」를 묻고, 오라클이 「예」 또는 「아니오」를 한 단계 만에 돌려준다. 이런 기계로 정의한 클래스를 P 위첨자 O, NP 위첨자 O 라 쓴다.
오라클 기계 — 기계는 계산 중에 오라클에 묻고, 답은 한 단계 만에 온다.

어떤 정리의 증명이 모든 오라클 O 에 대해 그대로 성립하면 그 증명은 상대화한다(relativize)고 말한다.

한 기계가 다른 기계를 한 단계씩 흉내 내는 논증은 상대화한다. 흉내 내는 쪽이 오라클 질문을 그대로 넘겨주면 되기 때문이다. 대각선 논법으로 얻는 P ≠ EXP 가 그 예로, 모든 오라클 A 에 대해 PA ≠ EXPA 가 성립한다.

Baker–Gill–Solovay 정리

증명된 정리 어떤 오라클 A 에 대해 PA = NPA 이고, 어떤 오라클 B 에 대해 PB ≠ NPB 이다.

Baker, Gill, Solovay 1975

A 만들기

A 를 PSPACE-완전 언어로 잡으면 PA = NPA = PSPACE 가 된다. 다항 공간 문제는 A 로 환원해 한 번 물으면 풀리고, 거꾸로 A 를 쓰는 비결정적 다항 시간 계산은 오라클의 답까지 스스로 계산해 가며 다항 공간 안에서 흉내 낼 수 있기 때문이다. 오라클이 워낙 강해서 결정적 기계와 비결정적 기계의 차이가 묻힌다.

B 만들기

  1. 언어 U(B) = { 1ⁿ : B 에 길이 n 인 문자열이 있다 } 를 생각한다. 비결정적 기계는 그런 문자열을 추측해 오라클에 물으면 되므로, B 가 무엇이든 U(B) ∈ NPB 다.
  2. 이제 B 를 단계별로 지어 다항 시간 오라클 기계가 모두 U(B) 를 틀리게 만든다. i 번째 단계에서는 i 번째 기계 Mᵢ 를, 지금까지 다룬 문자열보다 긴 길이 n 을 골라 입력 1ⁿ 으로 2ⁿ/10 단계까지 돌린다(다항 시간 기계라면 n 이 충분히 클 때 그 안에 멈춘다).
  3. 아직 정해지지 않은 문자열을 물으면 「B 에 없다」로 정한다.
  4. Mᵢ 가 받아들이면 길이 n 인 문자열을 B 에 하나도 넣지 않고, 거부하면 Mᵢ 가 묻지 않은 길이 n 문자열 하나를 B 에 넣는다. 길이 n 인 문자열은 2ⁿ 개인데 물은 것은 많아야 2ⁿ/10 개라 그런 문자열이 남아 있다.
  5. 어느 쪽이든 Mᵢ 의 답은 틀린다.

기계를 하나씩 속여 가는 이 구성은 그 자체가 대각선 논법이다.

Bennett 과 Gill 은 1981년에 오라클을 무작위로 골라도 확률 1 로 PB ≠ NPB 임을 보였다.

무엇을 뜻하는가

P = NP 를 상대화하는 논증으로 증명했다면 모든 오라클에 대해 PO = NPO 여야 하는데 B 가 반례다. P ≠ NP 를 그렇게 증명했다면 A 가 반례다. 따라서 상대화하는 논증만으로는 어느 쪽도 증명할 수 없다.

두 오라클 세계. 왼쪽 오라클 A(PSPACE-완전 언어)에서는 P 위첨자 A 와 NP 위첨자 A 가 같고, 오른쪽 오라클 B(대각선 논법으로 지은 언어)에서는 둘이 다르다. 상대화하는 논증으로 P ≠ NP 를 증명했다면 A 가 반례, P = NP 를 증명했다면 B 가 반례이므로, 상대화하는 논증만으로는 어느 쪽도 증명할 수 없다.
Baker–Gill–Solovay 정리가 장벽이 되는 이유 — 두 세계가 각각 한쪽 주장의 반례가 된다.

「대각선 논법만으로는 안 된다」는 말의 정확한 뜻이 이것이다. 대각선 논법을 쓰지 말라는 것이 아니다. 증명 어딘가에서 오라클을 달면 깨지는 성질, 곧 계산의 내부 구조를 써야 한다는 것이다. Aaronson 의 표현으로는, 증명이 어느 지점에선가 우리 세계에는 오라클이 없다는 사실을 「알아채야」 한다.

이 틈을 메우려는 시도도 있다. Aaronson 의 소개에 따르면 Arora·Impagliazzo·Vazirani 는 1992년 원고에서 이 장벽을 논리의 말로 다시 풀었다. 상대화하는 증명이란 복잡도 클래스를 「어떤 언어를 포함하고 어떤 연산에 닫혀 있는가」라는 공리로만 아는 증명이고, P ≠ NP 는 그 공리들로부터 독립이라는 것이다. 오라클 세계는 그 공리들의 모형 노릇을 한다.

상대화하지 않는 결과: IP = PSPACE

상대화하지 않는 증명은 실제로 있다. 대화형 증명(interactive proof)은 검증자가 무작위 질문을 던지며 증명자와 대화해 주장을 확인하는 방식이고, 그렇게 검증할 수 있는 문제의 클래스가 IP 다.

  • 1988년 Fortnow 와 Sipser 는 coNPA ⊄ IPA 인 오라클 A 를 만들었다. coNP 문제를 위한 대화형 증명은 상대화하는 기법으로는 찾을 수 없다는 뜻이다.
  • 그런데 1990년 Lund·Fortnow·Karloff·Nisan 이 coNP ⊆ IP 를, 곧이어 Shamir 가 IP = PSPACE 를 증명했다.

비결은 산술화(arithmetization)다. 논리식의 AND, OR, NOT 을 유한체 위의 곱셈과 덧셈으로 바꾸어 식 전체를 차수가 낮은 다항식으로 올리고, 0 과 1 이 아닌 점에서도 값을 계산한다. 식의 구조를 쓰는 일이라, 속을 들여다볼 수 없는 오라클 게이트가 끼어 있으면 할 수 없다.

AC⁰ 하한 같은 회로의 조합적 논증도 상대화에 걸리지 않는다. 그러나 상대화를 피했다고 P vs NP 에 닿는 것은 아니다. 조합적 논증은 자연 증명 장벽에, 산술화는 대수화 장벽에 걸린다.

출처

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

참고문헌 9

  • 장벽서지만 확인
    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 으로 확인.
    원문 주소 (doi.org)DOI 10.1137/0204037
  • 장벽서지만 확인
    Relative to a Random Oracle A, P^A ≠ NP^A ≠ co-NP^A with Probability 1C. H. Bennett, J. Gill · 1981SIAM Journal on Computing 10(1), 96–113쪽 (1981)

    오라클을 무작위로 골라도 확률 1 로 P 와 NP 가 갈림을 보인 논문이다. Baker–Gill–Solovay 정리의 후속 결과로, 2-2 의 상대화 글이 인용한다. SIAM 페이지로 연결된다.

    확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로 확인.
    원문 주소 (doi.org)DOI 10.1137/0210008
  • 장벽서지만 확인
    Are There Interactive Protocols for co-NP Languages?L. Fortnow, M. Sipser · 1988Information Processing Letters 28(5), 249–251쪽 (1988)

    coNP 가 IP 에 들어가지 않게 되는 오라클을 만든 논문이다. coNP 문제를 위한 대화형 증명은 상대화하는 기법으로는 찾을 수 없다는 뜻이다. 뒤에 증명된 IP = PSPACE 가 상대화하지 않는 결과임을 보여 주는 근거로, 2-2 의 상대화 글과 2-4 의 IP = PSPACE 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.1 로 확인.
    원문 주소 (doi.org)DOI 10.1016/0020-0190(88)90199-8
  • 부분 결과원문 확인
    Algebraic methods for interactive proof systemsCarsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan · 1992Journal of the ACM 39(4), 859–868쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 2–10쪽

    대화형 증명을 짓는 대수적 기법(산술화)을 도입해 다항 위계의 모든 문제가 대화형 증명을 가짐을 보인 논문이다. IP = PSPACE 와 PCP 정리로 이어지는 흐름의 출발점이다. 산술화가 어떻게 상대화 장벽을 넘는지 원문으로 보려는 독자에게 권한다. 공저자 Fortnow 의 누리집에 있는 공개본으로 연결한다.

    확인:저자 공개본을 열어 초록과 서론을 읽음.
    원문 주소 (lance.fortnow.com)
  • 부분 결과서지만 확인
    IP = PSPACEAdi Shamir · 1992Journal of the ACM 39(4), 869–877쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 11–15쪽

    대화형 증명으로 증명할 수 있는 문제의 모임이 정확히 PSPACE 임을 보인 논문이다. 상대화되지 않는 증명의 대표 사례다. 같은 호에 나란히 실린 lfkn-1992 의 기법 위에 서 있으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.1 과 Arora–Barak 공개 초고 8장의 역사 주석으로 확인.
    원문 주소 (doi.org)DOI 10.1145/146585.146609
  • 장벽미확인
    Relativizing versus Nonrelativizing Techniques: The Role of Local CheckabilityS. Arora, R. Impagliazzo, U. Vazirani · 1992미출간 원고 (1992)

    상대화 장벽을 논리의 말로 다시 풀려 한 1992년의 미출간 원고다. Aaronson 의 소개에 따르면, 상대화하는 증명을 복잡도 클래스를 몇 가지 공리로만 아는 증명으로 보고 P ≠ NP 가 그 공리들로부터 독립임을 논한다. 2-2 의 상대화 글이 인용한다. 원고의 주소를 확인하지 못해 링크가 없다.

    확인:원고를 열지 못했고 주소도 확인하지 못함. 서지와 내용은 Aaronson 2017 의 참고문헌 목록과 §6.1.2 의 소개로만 적음.
  • 교과서원문 확인
    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)
  • 개관원문 확인
    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 등록 기록으로 확인.
    원문 주소 (doi.org)DOI 10.1145/129712.129771

하위 정보 0

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

아직 없습니다.