HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-5 실패한 증명 시도와 교훈

증명 주장을 점검하는 다섯 가지 질문

P ≠ NP 를 증명했다는 글을 볼 때, 그리고 자기 아이디어를 남에게 보이기 전에 던져 볼 질문을 정리한다. 쉬운 문제에서는 왜 안 통하는가, 알려진 알고리즘을 모두 이겨 내는가, 세 장벽을 어디서 넘는가, 알려진 하한을 다시 얻는가, 글이 검증하기 좋게 짜여 있는가.

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

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

P ≠ NP 를 증명했다는 글을 볼 때, 그리고 자기 아이디어를 남에게 보이기 전에 던져 볼 질문 다섯 개를 정리한다. Scott Aaronson 이 적은 경고 표지 여덟 가지와 Richard Lipton 이 같은 때 적은 원리를 바탕으로 새로 짠 질문들이다.

점검표를 쓰기 전에

「P ≠ NP 를 증명했다」는 글은 꾸준히 나오고, 하나하나를 끝까지 읽어 줄 전문가의 시간은 모자란다. Scott Aaronson 은 2010년 Deolalikar 의 원고가 며칠 만에 검토된 일을 두고, 그런 헌신적인 수고는 주장이 더 잦아지면 감당할 수 없을 것이라고 썼다. 그래서 그는 원고를 훑으며 살필 경고 표지 여덟 가지를 적어 두었다. 이 글은 그 표지들과 Richard Lipton 이 같은 때 적은 원리를 바탕으로 질문 다섯 개를 새로 짠 것이다.

질문 1. 쉬운 사촌 문제에서는 왜 안 통하는가

3-SAT 은 NP-완전이지만 절마다 리터럴이 둘인 2-SAT 은 다항 시간에 풀린다. 연립 일차 방정식 꼴인 XOR-SAT 도, 그래프 2색칠도, 최대 매칭도 그렇다. 「3-SAT 은 어렵다」는 논증이 있다면, 3 을 2 로 바꾸었을 때 그 논증의 어느 줄이 무너지는지 바로 짚을 수 있어야 한다. 짚지 못하면 그 논증은 2-SAT 도 어렵다고 증명해 버린다. 거짓을 증명하는 논증은 어딘가 틀렸다.

두 줄로 된 흐름 그림. 윗줄: 어떤 논증이 「3-SAT 은 어렵다」는 결론을 낸다. 아랫줄: 같은 논증에서 3 을 2 로 바꾸면 「2-SAT 도 어렵다」는 결론이 나오는데, 2-SAT 은 다항 시간에 풀리므로 이 결론은 거짓이다. 오른쪽 상자에는 무너지는 줄을 짚지 못하면 그 논증은 거짓을 증명하므로 어딘가 틀렸다고 적혀 있다.
너무 많이 증명하는 증명. 논증을 조금 고쳤더니 거짓으로 알려진 명제까지 증명된다면, 원래 논증 어딘가가 틀린 것이다.

Lipton 은 이것을 일반 원리로 적었다. 명제 A 의 증명을 조금 고쳤더니 거짓으로 알려진 명제 B 까지 증명된다면 큰일이라는 것이다. Aaronson 은 자기가 본 시도는 모두 이 점검에 걸렸던 것 같다고 말한다.

양적인 판도 있다. 3-SAT 을 2ⁿ 가지 대입을 다 해 보지 않고 (4/3)ⁿ 시간쯤에 푸는 알고리즘이 알려져 있다. 그러니 「어떤 알고리즘이든 대입을 하나하나 다 살펴야 한다」로 귀결되는 논증은 틀렸다.

질문 2. 알려진 알고리즘을 모두 이겨 내는가

P ≠ NP 의 증명은 떠올릴 수 있는 알고리즘 몇 가지가 아니라 다항 시간 알고리즘 전부가 실패함을 보여야 한다. 그 「전부」에는 동적 계획법, 선형 계획법과 준정부호 계획법, 소거법, 매칭 알고리즘처럼 겉보기에 어려운 문제를 뜻밖의 길로 푸는 기법들이 들어 있다. 증명은 이 기법들이 왜 문제의 NP-완전 문제에는 듣지 않는지를 어떤 식으로든 「알고」 있어야 한다. 첫 질문보다 훨씬 엄한 요구다.

질문 3. 세 장벽을 어디서 넘는가

지금까지의 기법이 왜 P 대 NP 에 닿지 못하는지 설명하는 정리가 셋 있다.

상대화
모든 기계에 같은 오라클(신탁)을 달아도 그대로 성립하는 논증으로는 풀 수 없다(Baker–Gill–Solovay).
자연 증명
「이 함수는 쉬운 함수들과 달리 무작위 함수처럼 생겼다」는 꼴이면서 그 판별이 효율적인 논증은, 널리 믿는 암호학적 가정 아래 센 회로 클래스에는 통하지 않는다(Razborov–Rudich).
대수화
오라클의 낮은 차수 다항식 확장을 허용해도 그대로 성립하는 논증으로는 풀 수 없다(Aaronson–Wigderson).

따라서 증명은 어느 대목에서 오라클이 있으면 성립하지 않는 사실을 쓰는지, 왜 자연 증명이 아닌지 스스로 밝혀야 한다. 앞선 시도들을 좌절시킨 장벽을 어떻게, 왜 넘는지 설명하는 개요가 없는 것이 Aaronson 의 여섯째 표지다.

질문 4. 가는 길에 더 작은 결과가 나오는가

P ≠ NP 가 참이면 그보다 약한 명제들도 따라서 참이다. 그 가운데 P ≠ PSPACE 나 NEXP ⊄ P/poly 같은 것은 아직 증명되지 않았다. Aaronson 은 P 대 NP 를 지금 증명할 수 있는 것보다 수십 걸음 앞에 있는 문제로 보라고 하면서, 30걸음째와 40걸음째는 제쳐 두더라도 첫걸음들은 어디 있느냐고 묻는다.

거꾸로 이미 증명된 하한도 있다. 상수 깊이 회로에 대한 하한, Razborov 의 단조 회로 하한이 그렇다. Aaronson 에 따르면 이런 결과들은 적어도 균일한 판에서는 P ≠ NP 에서 따라 나온다. 그러므로 P ≠ NP 의 증명이라면 그 안에서 이 결과들이 어떻게 다시 나오는지 보일 수 있어야 한다.

질문 5. 글이 검증하기 좋게 짜여 있는가

  • 보조정리, 정리, 증명으로 나뉘어 있는가. Aaronson 은 이 형식이 프로그램을 모듈로 나누는 것과 같아서 오류를 찾는 속도를 크게 높인다고 말한다.
  • 정의의 미세한 차이에 결론이 걸려 있지 않은가. 그는 논리로 복잡도 클래스를 규정하는 분야를 예로 든다. 순서 관계가 있느냐 없느냐 같은 부호화의 작은 차이가 계산 복잡도의 큰 차이에 대응하기 때문에 스스로를 속이기 쉽다는 것이다.
  • 확인되기 전에 성과의 의미를 길게 말하고 있지 않은가. 그는 초고에서부터 드러나는 과신을 마지막 표지로 꼽는다.

자기 아이디어에 쓰는 순서

  1. 논증을 2-SAT 과 XOR-SAT 에 그대로 적용해 본다. 막히는 줄이 없으면 거기서 멈춘다.
  2. 모든 기계에 오라클을 달아 본다. 논증이 한 줄도 바뀌지 않으면 상대화 장벽에 걸린 것이다.
  3. 목표를 낮춰 본다. 같은 생각으로 이미 알려진 하한 하나를 다시 증명할 수 있는지 본다.
  4. 정의와 보조정리를 나누어 적고, 보조정리마다 따로 의심한다.
  5. 그런 다음 남에게 보인다. 주장은 다른 사람이 읽고 따져 본 뒤에야 증명이 된다.

출처

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

참고문헌 6

  • 증명 주장원문 확인
    Eight Signs A Claimed P≠NP Proof Is WrongScott Aaronson · 2010블로그 Shtetl-Optimized, 2010년 8월 13일

    P ≠ NP 증명 주장이 틀렸을 가능성이 큼을 알려 주는 여덟 가지 징후를 정리한 글이다. 「같은 논증이 2-SAT 에는 왜 통하지 않는지 설명하지 못한다」, 「더 약한 결과나 이미 알려진 하한을 도중에 얻지 못한다」, 「앞선 시도를 막은 장벽을 어떻게 넘는지 말하지 않는다」 같은 점검 항목을 든다. 자기 아이디어를 스스로 점검하려는 도전자와 증명 주장을 가려 읽으려는 독자 모두에게 쓸모 있다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (scottaaronson.blog)
  • 증명 주장원문 확인
    Deolalikar Responds To Issues About His P≠NP ProofR. J. Lipton · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 11일

    Terence Tao 의 세 질문과 Deolalikar 의 답변을 소개한 Lipton 의 블로그 글이다. 「증명을 조금 고쳤더니 거짓으로 알려진 명제까지 증명된다면 큰일」이라는 원리(The Principle)도 이 글에 있다. 2-5 의 Deolalikar 사례 글과 점검 질문 글이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.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)
  • 장벽원문 확인
    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 등록 기록으로 확인.
    원문 주소 (doi.org)DOI 10.1006/jcss.1997.1494
  • 장벽원문 확인
    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)
  • 장벽서지만 확인
    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

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

아직 없습니다.