HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-4 알려진 부분 결과

IP = PSPACE — 묻고 답하며 확인할 수 있는 것의 범위

무작위로 질문을 던지는 다항 시간 검증자가 전능한 증명자와 대화해 확인할 수 있는 문제는 정확히 다항 공간 문제다. Lund–Fortnow–Karloff–Nisan 과 Shamir 가 산술화 기법으로 증명했으며, 상대화하지 않는 증명의 대표 사례다.

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

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

무작위로 질문을 던지는 다항 시간 검증자가 전능한 증명자와 대화해 확인할 수 있는 문제는 정확히 다항 공간 문제다. 이 글은 IP = PSPACE 의 진술과 산술화를 쓴 증명의 얼개를 보고, 이것이 상대화하지 않는 증명의 대표 사례라는 뜻을 짚는다.

정확한 진술

대화형 증명 체계(interactive proof system)에는 두 참여자가 있다. 증명자는 계산 능력에 제한이 없지만 믿을 수 없다. 검증자는 동전을 던질 수 있는 다항 시간 알고리즘이다. 둘은 입력 x 를 함께 보며 메시지를 다항 번 주고받고, 마지막에 검증자가 받아들일지 정한다.

비유 삽화. 왼쪽에는 별과 책에 둘러싸여 무엇이든 알 것 같지만 장난스러운 표정으로 손가락을 꼬고 있는 커다란 인물(증명자)이 있고, 오른쪽에는 작은 책상 앞에서 동전을 던지며 날카롭게 질문하는 꼼꼼한 심사관(검증자)이 있다. 둘 사이로 말풍선이 오간다.
비유: 무엇이든 알지만 믿을 수는 없는 증명자와, 동전을 던져 무작위로 질문하는 검증자. AI 생성 그림
IP
언어 L 이 클래스 IP 에 속한다는 것은 다음 두 조건을 채우는 검증자가 있다는 뜻이다.
  • x ∈ L 이면, 검증자가 2/3 이상의 확률로 받아들이게 만드는 증명자의 전략이 있다.
  • x ∉ L 이면, 증명자가 어떤 전략을 쓰든 검증자는 2/3 이상의 확률로 거부한다.
PSPACE
PSPACE 는 다항식 크기의 기억 공간으로 판정되는 언어의 클래스다.

정리 증명됨

IP = PSPACE.

Lund–Fortnow–Karloff–Nisan, Shamir

대화형 증명이라는 모형은 1985년에 Goldwasser, Micali, Rackoff 와 Babai 가 내놓았다. 위 정리를 이루는 두 논문은 1990년 학회(FOCS)에서 발표되어 1992년 Journal of the ACM 의 같은 호에 나란히 실렸다.

뜻

NP — 가장 단순한 경우

NP 는 이 모형의 가장 단순한 경우다. 증명자가 증거를 한 번 건네고, 검증자는 동전 없이 확인한다.

IP — 무작위와 대화를 허용

여기에 무작위와 대화를 허용하면 확인할 수 있는 범위가 PSPACE 전체로 넓어진다는 것이 이 정리다. PSPACE 는 NP 를 포함하며 훨씬 클 것으로 여겨지는 클래스다.

당시의 통념은 반대였다. 교과서의 역사 주석에 따르면 대화형 증명은 NP 를 조금 넓힌 정도이고 3SAT 식이 충족 불가능하다는 것조차 대화로는 증명할 수 없으리라는 것이 일반적인 느낌이었다. 전개는 빨랐다. 1989년 12월 Nisan 이 동료들에게 보낸 이메일이 발단이 되었다. 그것을 받은 Lund, Fortnow, Karloff 가 Nisan 을 공저자로 하여 다항 위계 전체가 IP 에 들어감을 보였고, 곧 Shamir 가 IP = PSPACE 를 증명했다.

증명의 핵심 생각 — 산술화

IP ⊆ PSPACE 쪽은 어렵지 않다. 대화 전체를 증명자와 검증자의 게임으로 보고 게임 나무를 다항 공간에서 훑으면 된다. 어려운 쪽은 PSPACE ⊆ IP 이고, 그 열쇠가 산술화(arithmetization)다.

논리식을 다항식으로 옮기기

논리식을 유한체 위의 다항식으로 옮긴다. x AND y 는 xy 로, NOT x 는 1 − x 로, x OR y 는 x + y − xy 로 바꾼다. 변수에 0 과 1 만 넣으면 원래 논리식과 값이 같지만, 이제는 다른 수도 넣을 수 있다.

손으로 확인해 보면, x 가 1 이고 y 가 0 일 때 xy 는 0, x + y − xy 는 1, 1 − x 는 0 이다. 각각 AND, OR, NOT 의 값과 같다.

「3SAT 식 φ 를 충족하는 대입이 없다」를 증명하는 경우로 얼개를 보자. φ 를 옮긴 다항식을 q 라 하면, 증명할 것은 0 과 1 로 된 모든 대입에 걸친 q 값의 합이 0 이라는 등식이다. 항이 2ⁿ 개라서 검증자가 직접 더할 수는 없다.

  1. 증명자가 첫 변수만 남기고 나머지 변수에 대해 합한 일변수 다항식 q₁ 을 보낸다.
  2. 검증자는 q₁(0) + q₁(1) = 0 인지 확인하고, 체에서 무작위로 고른 원소 r₁ 을 보낸다.
  3. 증명자는 첫 변수를 r₁ 로 고정하고 둘째 변수만 남긴 다항식 q₂ 를 보낸다. 검증자는 q₂(0) + q₂(1) = q₁(r₁) 인지 확인하고 r₂ 를 고른다. 이것을 변수 수만큼 되풀이한다.
  4. 마지막에는 변수가 모두 고정되어 검증자가 q 값을 직접 계산해 맞춰 볼 수 있다.
증명자와 검증자의 대화를 위에서 아래로 그린 그림. 맨 위에 증명할 것은 0 과 1 로 된 모든 대입에 걸친 q 값의 합이 0 이라는 등식이라고 적혀 있다. 왼쪽 증명자에서 오른쪽 검증자로 q₁ 이 가고, 검증자는 q₁(0) + q₁(1) = 0 인지 확인한 뒤 무작위 r₁ 을 돌려보낸다. 다시 q₂ 가 가고 검증자는 q₂(0) + q₂(1) = q₁(r₁) 인지 확인한 뒤 r₂ 를 보낸다. 이것을 변수 수만큼 되풀이하고, 마지막에 검증자가 q 값을 직접 계산해 맞춰 본다. 아래에는 차수 d 이하의 서로 다른 두 일변수 다항식은 많아야 d 개의 점에서만 값이 같으므로 거짓 다항식은 무작위 점에서 탄로 날 확률이 매우 높다고 적혀 있다.
합 검사 대화의 흐름. 검증자는 한 번에 일변수 다항식 하나만 받아 두 값의 합을 맞춰 보고, 무작위 점을 골라 다음 단계로 넘긴다.

증명자가 중간에 거짓 다항식을 보냈다고 하자. 차수가 d 이하인 서로 다른 두 일변수 다항식은 많아야 d 개의 점에서만 값이 같다. 체가 충분히 크면 무작위로 고른 점에서 거짓이 탄로 날 확률이 매우 높다. Shamir 는 이 방법을 한정 기호가 붙은 논리식으로 넓혀 PSPACE 전체를 덮었다.

상대화하지 않는 결과라는 의미

Baker, Gill, Solovay 의 1975년 결과는 「모든 기계에 같은 오라클(신탁)을 달아도 그대로 성립하는 증명」, 곧 상대화(relativization)하는 증명으로는 P 대 NP 를 풀 수 없음을 보였다. 그런데 그때까지 알려진 기법은 거의 다 상대화했다.

IP = PSPACE 는 그렇지 않다. Fortnow 와 Sipser 는 1988년에 coNP 가 IP 에 들어가지 않게 되는 오라클을 만들어 두었다. coNP ⊆ PSPACE 는 어떤 오라클을 달아도 성립하므로, 그 오라클 아래에서는 IP 와 PSPACE 가 다르다. 그러니 IP = PSPACE 의 증명은 상대화할 수 없다. 실제로 Lund 등의 논문은 "Our result does not relativize." 라고 적고 있다.

어디서 갈리는지도 보인다. 산술화는 논리식이 AND, OR, NOT 으로 짜여 있다는 구조를 이용한다. 속을 알 수 없는 오라클 게이트는 다항식으로 옮길 수 없다. Aaronson 은 이 정리가 상대화 장벽이 진전을 막지 못한다는 것을 극적으로 보여 주었다고 평가한다.

P 대 NP 까지의 거리

  • IP = PSPACE 는 두 클래스가 같다는 결과다. P ≠ NP 는 두 클래스가 다르다는 주장이고, 이 정리에서 곧바로 나오는 것은 없다.
  • 산술화에도 한계가 있다. Aaronson 과 Wigderson 은 2008년에 대수화(algebrization) 장벽을 내놓았다. 오라클뿐 아니라 그 오라클을 유한체 위의 낮은 차수 다항식으로 넓힌 것까지 쓰게 해 주면, 산술화에 기댄 결과들은 다시 그대로 성립한다. 반면 P 대 NP 는 그런 기법으로는 어느 쪽으로도 풀 수 없다.

그래도 이 정리는 장벽 하나를 실제로 넘어 본 경험이었고, 대화형 증명 연구는 PCP 정리의 바탕이 되었으며 Williams 의 회로 하한 증명에도 재료로 쓰였다.

출처

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

참고문헌 7

  • 부분 결과원문 확인
    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)
  • 개관원문 확인
    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)
  • 교과서원문 확인
    Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009

    계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.

    확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
    원문 주소 (theory.cs.princeton.edu)
  • 장벽원문 확인
    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 을 읽음.
    원문 주소 (www.scottaaronson.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
  • 장벽서지만 확인
    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
  • 장벽서지만 확인
    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

하위 정보 0

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

아직 없습니다.