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

2010년 Deolalikar 의 P ≠ NP 증명 주장 — 공개 검토의 기록

2010년 8월 HP 연구소의 Vinay Deolalikar 가 P ≠ NP 의 증명이라며 원고를 돌리자, 연구자들은 블로그와 위키에서 며칠 만에 공개 검토를 벌였다. 무엇이 주장되었고 어떻게 검토되었으며 어떤 문제가 지적되었는지를 공개 기록에 남은 사실만으로 따라간다.

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

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

2010년 8월 HP 연구소의 Vinay Deolalikar 가 P ≠ NP 의 증명이라며 원고를 돌리자, 연구자들은 블로그와 위키에서 며칠 만에 공개 검토를 벌였다. 이 글은 무엇이 주장되었고 어떻게 검토되었으며 어떤 문제가 지적되었는지를 공개 기록에 남은 사실만으로 따라간다.

무엇을 주장했나

2010년 8월 6일, HP 연구소의 Vinay Deolalikar 는 「P ≠ NP」라는 제목의 원고를 이 분야 연구자 몇 사람에게 보냈다. 첫 판은 66쪽이었고, 며칠 사이 고쳐 쓴 판은 100쪽을 조금 넘었다.

원고의 초록은 NP 가 P 와 다름을 보인다고 밝힌다. 재료는 두 분야에서 왔다.

  • 유한 모형 이론. 순서가 주어진 구조 위에서는 「일차 논리에 최소 고정점 연산을 더한 논리 FO(LFP)」로 적을 수 있는 성질과 다항 시간에 계산되는 성질이 일치한다는 Immerman 과 Vardi 의 정리가 있다.
  • 통계 물리학. 무작위로 만든 k-SAT 식은 절이 충분히 많아지면 해들이 서로 멀리 떨어진 아주 많은 무리로 쪼개진다.

Lipton 의 요약을 빌리면 논증의 뼈대는 이렇다. P = NP 라면 SAT 의 해 공간은 FO(LFP) 로 적을 수 있는 만큼 단순한 구조여야 한다. 그런데 무작위 k-SAT 의 해 공간은 그렇게 단순하지 않다. 그러므로 모순이다.

공개 검토는 어떻게 이루어졌나

검토는 학술지 심사가 아니라 인터넷에서, 며칠 만에 이루어졌다. Polymath 위키에 남은 연표와 블로그 글에서 날짜를 추리면 다음과 같다.

  1. Deolalikar 가 원고를 연구자 몇 사람에게 보냄
  2. 원고가 블로그와 뉴스 모음 사이트에 알려짐. Lipton 이 블로그에 첫 글을 씀
  3. Lipton 과 Regan 이 댓글에서 나온 주요 반론 네 가지를 정리. 흩어진 기술적 지적을 모은 공동 문서가 만들어져 이튿날 위키로 옮겨짐
  4. Lipton 이 Terence Tao 의 세 질문과 Deolalikar 의 답변을 소개. 셋째 판 원고가 올라옴
  5. Neil Immerman 의 편지가 공개됨
  6. Deolalikar 가 3쪽짜리 개요를 올림
  7. Lipton 과 Regan 이 일주일의 논의를 정리

Lipton 은 첫 글에서 원고를 진지한 연구자가 쓴 길고 잘 쓰인 논문이라고 소개했다. 논의에는 Tao 와 Timothy Gowers 두 필즈상 수상자를 비롯한 많은 연구자가 참여했다. 위키 페이지는 머리말에서 새로 싣는 내용은 건설적이고 객관적으로 중립이어야 하며 개인적 추측은 피한다는 원칙을 밝혔다.

Scott Aaronson 은 다른 방식으로 의견을 냈다. 9일의 글에서 그는 원고를 자세히 읽지 못했다고 밝히면서, Deolalikar 가 이 증명으로 Clay 상금을 받으면 자기 돈 20만 달러를 보태겠다고 썼다. 증명이 성립하지 않으리라는 예측을 그렇게 표현한 것이다. 같은 글에서 그는 원고가 잘 쓰였고 생각해 볼 만한 새 발상을 담고 있다고도 적었다.

어떤 문제가 지적되었나

Lipton 과 Regan 은 15일의 정리에서 쟁점을 둘로 묶었다.

쉬운 문제와 구별되지 않는다

2-SAT 과 XOR-SAT 은 다항 시간에 풀린다. XOR-SAT 은 2 를 법으로 하는 연립 일차 방정식이어서 소거법으로 풀린다. 검토자들이 먼저 물은 것은 이 논증이 왜 그런 문제에는 통하지 않느냐였다. 해 공간의 구조만으로 「어렵다」를 끌어내는 논증이 쉬운 문제에도 똑같이 적용된다면 틀린 결론이 나오기 때문이다. Ryan Williams 는 식에 든 리터럴의 부호를 뒤집어, 해 공간의 모양은 그대로 두면서 문제를 뻔하게 만드는 변환을 보였다. Deolalikar 는 XOR-SAT 은 선형이라 해 공간을 간단히 적을 수 있고 2-SAT 은 문제가 되는 상(phase)에 들어가지 않는다고 답했다. Lipton 과 Regan 은 납득할 만한 답이 보이지 않는다고 정리했다.

유한 모형 이론을 쓰는 방식

Immerman 은 편지에서 두 가지를 지적했다. 고정점 계산의 각 단계가 순서와 무관하다는 주장은 참이 아니다. 그리고 원고는 고정점을 단항 관계로, 순서를 「바로 다음」 관계로 제한하는데, 그 범위에서는 FO(LFP) 가 P 전체를 표현하지 못한다. 그렇다면 논증이 다루는 것은 P 가 아니라 그보다 작은 클래스다. Lipton 과 Regan 은 15일 시점에 이 지적을 반박한 사람이 없다고 적었다.

Lipton 이 11일에 소개한 Tao 의 정리는 쟁점을 세 단계로 나눈다. 작은 수정으로 증명이 되는가, 큰 수정으로 되는가, 이 전략 자체에 가망이 있는가. Tao 는 첫째 답은 「아니오」로 보이고 둘째는 「상당한 새 발상 없이는 아마도 아니오」이며 셋째는 아직 열려 있다고 보았다.

결말

8월 13일 Aaronson 은 증명이 지금 모습으로는 치명적인 결함이 있다는 데 분명한 합의가 이루어졌다고 적었다. 위키의 연표에 따르면 17일에 원고는 저자의 누리집에서 모두 내려졌다. 저자는 제기된 문제를 고친 126쪽의 수정 원고를 학술지 심사에 보내겠다고 알렸다.

1년 뒤 Lipton 은 달라진 것이 없다고 전했다. 저자의 누리집은 여전히 결과를 주장하며 학술지 심사 중이라고 설명하고 있었고, 수정 원고는 공개되지 않았다. Aaronson 의 2017년 개관은 이 일을 그때까지 가장 큰 주목을 받은 P ≠ NP 증명 시도로 꼽는다. 그리고 원고가 쓰는 통계적 성질로는 무작위 XOR-SAT 의 해 집합을 무작위 3-SAT 의 해 집합과 구별할 수 없다는 지적을 핵심으로 정리한다. 이 글을 쓰며 확인한 기록 어디에도 수정 원고가 심사를 통과했다는 내용은 없다.

남은 것

Lipton 과 Regan 은 1년 뒤의 글에서 몇 가지 교훈을 꼽았다.

  • 이 문제에 대한 관심이 예상보다 훨씬 컸다.
  • 웹은 수학적 주장을 이해하는 데 큰 힘을 발휘했다.
  • 다른 분야에서 온 저자가 새 증명을 설명하는 일은 매우 어렵다.
  • 온라인의 독자는 빠른 판정을 바라지만 복잡한 수학적 논증은 본디 그것을 허락하지 않는다.

두 사람은 논의 초기에 이렇게도 적었다. 옳든 그르든 이 어려운 문제를 생각하고 그 생각을 공동체와 나눈 저자에게 고마워해야 한다는 것이다. 한편 Aaronson 은 이 일을 겪고 「어떤 주장이 읽을 만한지 가려내는 표지」를 글로 정리했다. 다음 글이 그것을 다룬다.

출처

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

참고문헌 11

  • 증명 주장원문 확인
    P ≠ NPVinay Deolalikar · 2010미출판 원고 (HP Research Labs, 2010년 8월 6일 판, 66쪽) · G. Woeginger 의 P-versus-NP 페이지에 보관된 사본

    2010년 8월에 공개되어 큰 관심을 모았고 며칠 만에 공개 검토를 받은 P ≠ NP 증명 주장의 원고다. 공개 검토에서 Immerman, Tao 등 여러 연구자가 찾아낸 문제는 두 갈래(P 를 논리로 규정하는 부분의 잘못된 사용, k-SAT 해 공간의 구조에 기댄 논증의 결함)로 요약되었다(lipton-regan-2010-08-15 카드의 글). 이 증명 주장은 받아들여지지 않았다. 그럴듯한 증명 주장이 어떻게 검증되는지 보여 주는 사례로, 2-5 를 읽는 독자에게 권한다. 연결한 것은 Woeginger 의 P-versus-NP 페이지에 보관된 원고 사본이다.

    확인:Woeginger 의 페이지에 보관된 원고 사본(2010-08-06 판, 66쪽)을 열어 표지와 초록을 확인. 논증의 내용은 Lipton 의 요약 등 공개 검토 기록에 기댐.
    원문 주소 (wscor.win.tue.nl)
  • 증명 주장원문 확인
    Deolalikar P vs NP paperPolymath1Wiki 기여자들 · 2010Polymath1Wiki (원 주소는 사라져 Internet Archive 의 2013-01-15 사본으로 확인)

    Deolalikar 원고에 대한 기술적 지적과 날짜별 경과를 연구자들이 함께 정리한 위키 문서다. 2-5 의 Deolalikar 사례 글이 날짜별 연표의 출처로 쓴다. 원 주소가 사라져 Internet Archive 의 2013년 1월 15일 사본으로 연결한다.

    확인:Internet Archive 사본을 열어 머리말과 Timeline 절을 읽음.
    원문 주소 (web.archive.org)
  • 증명 주장원문 확인
    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 의 장벽 개관이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.com)
  • 증명 주장원문 확인
    Issues In The Proof That P≠NPR. J. Lipton, K. W. Regan · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 9일

    Deolalikar 원고에 대해 댓글에서 나온 주요 반론 네 가지를 정리한 Lipton 과 Regan 의 블로그 글이다. 어려운 문제에 도전하는 사람이 더 많아져야 한다는 말도 이 글에 있다. 2-5 의 증명 주장 개관과 Deolalikar 사례 글이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.com)
  • 증명 주장원문 확인
    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)
  • 증명 주장원문 확인
    Fatal Flaws in Deolalikar's Proof?R. J. Lipton · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 12일 (Neil Immerman 의 편지 전문 수록)

    Neil Immerman 이 Deolalikar 원고의 결함을 지적한 편지 전문을 실은 Lipton 의 블로그 글이다. 유한 모형 이론을 쓰는 방식에 대한 두 가지 지적이 담겨 있다. 2-5 의 Deolalikar 사례 글이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.com)
  • 증명 주장원문 확인
    The P≠NP “Proof” Is One Week OldR. J. Lipton, K. W. Regan · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 15일

    Deolalikar 원고를 둘러싼 일주일의 논의를 두 쟁점으로 정리한 Lipton 과 Regan 의 블로그 글이다. 쉬운 문제(2-SAT·XOR-SAT)와 구별되지 않는다는 지적과, 유한 모형 이론을 쓰는 방식의 문제를 요약한다. 2-5 의 Deolalikar 사례 글이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.com)
  • 증명 주장원문 확인
    Deolalikar's Claim: One Year LaterR. J. Lipton · 2011블로그 Gödel's Lost Letter and P=NP, 2011년 8월 11일

    Deolalikar 의 주장이 나온 지 1년 뒤의 상태와 교훈을 정리한 블로그 글이다. 수정 원고가 공개되지 않았다는 것과, 공개 검토에서 얻은 교훈 몇 가지를 적는다. 2-5 의 Deolalikar 사례 글이 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (rjlipton.com)
  • 증명 주장원문 확인
    Putting my money where my mouth isn'tScott Aaronson · 2010블로그 Shtetl-Optimized, 2010년 8월 9일

    Deolalikar 의 원고가 돌던 2010년 8월 9일, Aaronson 이 증명이 성립하지 않으리라는 예측을 내기로 표현한 블로그 글이다. 원고를 자세히 읽지 못했다고 밝히면서, 이 증명으로 Clay 상금이 주어지면 자기 돈 20만 달러를 보태겠다고 썼다. 2-5 의 Deolalikar 사례 글이 공개 검토의 한 장면으로 인용한다.

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (scottaaronson.blog)
  • 증명 주장원문 확인
    Eight Signs A Claimed P≠NP Proof Is WrongScott Aaronson · 2010블로그 Shtetl-Optimized, 2010년 8월 13일

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

    확인:블로그 글을 직접 열어 읽음.
    원문 주소 (scottaaronson.blog)
  • 개관원문 확인
    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)

하위 정보 0

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

아직 없습니다.