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

해마다 나오는 「증명했다」 — 그리고 아직 인정된 증명은 없다

P 대 NP 를 풀었다는 주장은 양쪽 방향으로 꾸준히 나온다. Gerhard Woeginger 가 모아 둔 목록을 직접 세어 보고, 그럼에도 학계가 받아들인 증명은 하나도 없다는 사실과, 실패한 시도가 좋은 정리를 낳은 사례를 살핀다.

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

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

P 대 NP 를 풀었다는 주장은 양쪽 방향으로 꾸준히 나온다. 이 글은 Gerhard Woeginger 가 모아 둔 목록을 직접 세어 보고, 그럼에도 학계가 받아들인 증명은 하나도 없다는 사실과, 실패한 시도가 좋은 정리를 낳은 사례를 살핀다.

목록으로 남은 주장들

P 대 NP 문제를 풀었다는 논문은 드물지 않다. Gerhard Woeginger 는 그런 논문의 링크를 한 페이지에 모아 두었다. 제목은 「The P-versus-NP page」이고, 첫머리에 이 문제를 어느 쪽으로든 해결하려는 논문을 모은다고 밝히고 있다. 페이지에 적힌 마지막 수정일은 2016년 9월 26일이다.

이 페이지를 2026년 10월에 열어 직접 세어 본 결과는 이렇다.

  • 「같다」, 「다르다」 같은 분류 표지가 붙은 항목은 114개다.
  • 첫 항목은 1986~87년 Ted Swart 의 논문들이고, 마지막 항목은 2016년 9월의 것이다. 30년에 걸친 목록이다.
  • 표지를 종류별로 세면 [Equal](P = NP) 62, [Not equal](P ≠ NP) 50, [Unprovable](증명 불가능) 2, [Undecidable](결정 불가능) 1 이다. 한 항목은 [Equal] 과 [Not equal] 을 함께 달고 있다.
  • 항목 첫머리에 적힌 연도로 보면 2002년부터 2016년까지는 한 해도 거르지 않는다. 가장 많은 해는 2011년으로 14개다.
가로 막대그래프. Woeginger 의 목록에서 분류 표지별 항목 수를 2026년 10월에 직접 센 값이다. [Equal](P = NP) 62, [Not equal](P ≠ NP) 50, [Unprovable](증명 불가능) 2, [Undecidable](결정 불가능) 1. 아래에 표지가 붙은 항목은 114개이고 한 항목은 [Equal] 과 [Not equal] 을 함께 달고 있다고 적혀 있다.
Woeginger 의 목록을 분류 표지별로 센 값(2026년 10월). 한 항목이 두 표지를 함께 달고 있어 막대의 합은 항목 수 114 보다 하나 많다.

목록은 계속 자라 왔다. 2012년 SIGACT News 의 한 칼럼 머리말은 이 페이지가 80편이 넘는 논문을 잇고 있다고 소개했는데, 4년 뒤에는 위의 수가 되었다. 이 목록이 전부도 아니다. 목록은 2016년에서 멈췄고, 그전에도 관리자에게 알려진 것만 실렸다. Aaronson 은 2017년 개관에서 P ≠ NP 쪽만 해도 수십 년 동안 수백 건의 잘못된 증명이 발표되었다고 적는다.

인정된 증명은 없다

이 가운데 학계가 받아들인 증명은 없다. Clay 수학연구소의 밀레니엄 문제 페이지는 P 대 NP 를 「Unsolved」로 표시하고 있다(2026년 10월 확인). 밀레니엄 문제에는 문제마다 100만 달러의 상금이 걸려 있다.

Woeginger 는 목록 앞에 눈여겨볼 주석을 달아 두었다. 목록의 논문 가운데 심사를 거치는 학술지에 실리고, 그 분야 전문가들이 철저히 검증했으며, 연구자 사회가 옳다고 받아들인 것은 Mihalis Yannakakis 의 논문 하나뿐이라는 것이다. 그리고 그 논문은 문제를 푼 것이 아니다. 주석의 표현으로는 그 논문은 문제를 해결하는 어떤 접근법이 결코 성공하지 못한다는 것을 보였을 「뿐」이다.

전문가들의 체감도 다르지 않다. Gasarch 는 2019년 설문 보고서에서 2012년 이후 P 대 NP 의 해결 쪽으로는 진전이 거의, 어쩌면 전혀 없었다고 적었다.

실패한 주장이 낳은 정리

Yannakakis 의 논문이 왜 이 목록에 있는지는 첫 항목이 설명한다.

  1. 에 Ted Swart 는 해밀턴 순환 문제를 다항식 크기의 선형 계획 문제로 적었다고 주장하는 논문들을 썼다. 선형 계획 문제는 다항 시간에 풀리고 해밀턴 순환 문제는 NP-난해이므로, 맞다면 P = NP 다.
  2. Yannakakis 가 이 논의를 끝냈다. 외판원 문제를 Swart 의 방식처럼 대칭적인 선형 계획으로 나타내려면 지수 크기가 필요함을 증명한 것이다. 학회 발표는 1988년, 학술지 게재는 1991년이다.

틀린 주장 하나가 「이런 식의 접근은 통할 수 없다」는 엄밀한 정리를 불러냈다. Aaronson 은 Swart 의 시도를 두고 역사상 가장 생산적인 실패한 P = NP 증명일지도 모른다고 썼다. 그의 개관에 따르면 2012년 이후에는 대칭 조건 없이도 같은 종류의 하한이 증명되었다.

이 사실을 어떻게 읽을까

  • 주장이 많다는 것이 문제가 쉽다는 뜻은 아니다. 오히려 문장은 짧고 뜻은 누구나 알아듣는데 증명은 어렵다는, 이 문제의 생김새를 보여 준다.
  • 주장을 내놓는 일 자체는 잘못이 아니다. Lipton 과 Regan 은 2010년의 한 주장을 검토하는 글에서, 어려운 문제에 도전하는 사람이 더 많아져야 하고 아무도 하지 않으면 문제는 영영 풀리지 않는다고 적었다.
  • 다만 주장은 증명이 아니다. 증명은 다른 사람들이 읽고 따져 본 뒤에야 증명으로 받아들여진다.
  • 실패에도 되풀이되는 모양이 있다. Aaronson 은 자기가 아는 잘못된 P ≠ NP 증명은 모두 같은 이유로 기각할 수 있었다고 말한다. 그 논법이 통한다면 P 에 속한다고 이미 알려진 문제에도 똑같이 초다항식 하한이 나와 버린다는 것이다.

마지막 관찰이 다음 두 글의 주제다. 2010년의 사례 하나를 자세히 보고, 주장을 점검하는 질문들을 정리한다.

출처

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

참고문헌 9

  • 증명 주장원문 확인
    The P-versus-NP pageGerhard J. Woeginger · 2016개인 웹 페이지 (에인트호번 공과대학교 누리집에 보존 · 마지막 고침 2016년 9월 26일)

    P 대 NP 를 어느 쪽으로든 해결했다고 주장하는 글들을 대체로 시간순으로 모아 둔 목록이다. 1986년부터 2016년까지 100건이 넘는 주장이 「같다」·「다르다」 등으로 분류되어 있다. 어느 것도 학계에서 해결로 받아들여지지 않았다. 새 아이디어를 내기 전에 비슷한 시도가 있었는지 살펴보기에 좋다. 2016년 9월 뒤로는 갱신되지 않았다.

    확인:2026-10-05 에 페이지를 직접 열어 머리말과 주석을 읽고 항목 수를 셈.
    원문 주소 (wscor.win.tue.nl)
  • 보조 자료원문 확인
    P vs NPClay Mathematics Institute · 2026Clay Mathematics Institute 웹 페이지 (2026-10-05 확인)

    Clay 수학연구소의 P 대 NP 문제 소개 페이지다. 기숙사 배정의 예로 문제를 설명하고, Cook 과 Levin 이 1971년에 독립적으로 문제를 정식화했다고 적으며, 문제의 상태를 「Unsolved」로 표시한다. 공식 문제 기술 PDF 로 가는 링크가 이 페이지에 있다.

    확인:2026-10-05 에 페이지를 직접 열어 읽음(상태 표기 「Unsolved」 확인).
    원문 주소 (www.claymath.org)
  • 보조 자료원문 확인
    The Millennium Prize ProblemsClay Mathematics Institute · 2026Clay Mathematics Institute 웹 페이지 (2026-10-05 확인)

    Clay 수학연구소가 일곱 밀레니엄 문제를 소개하는 공식 페이지다. 2000년 5월 24일 파리 발표와 문제마다 100만 달러의 상금이 적혀 있다. 1-1 의 역사 글과 2-5 의 증명 주장 개관이 날짜와 상금의 출처로 쓴다.

    확인:2026-10-05 에 페이지를 직접 열어 읽음.
    원문 주소 (www.claymath.org)
  • 개관원문 확인
    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)
  • 설문원문 확인
    Guest Column: The Second P=?NP PollWilliam I. Gasarch · 2012ACM SIGACT News 43(2), 53–77쪽 (2012) — SIGACT News Complexity Theory Column 74 (Lane A. Hemaspaandra 엮음)

    10년 뒤 같은 질문을 다시 던진 두 번째 설문 보고다. P ≠ NP 라는 답이 126명(83%)으로 2002년의 61%에서 크게 늘었다. 언제 풀릴지, 어떤 기법이 쓰일지에 대한 답과 응답자 의견 발췌가 실려 있다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 집계와 칼럼 머리말을 읽음.
    원문 주소 (www.cs.umd.edu)
  • 설문원문 확인
    Guest Column: The Third P=?NP PollWilliam I. Gasarch · 2019ACM SIGACT News 50(1), 38–59쪽 (2019) — SIGACT News Complexity Theory Column 100 (Lane A. Hemaspaandra 엮음)

    세 번째 설문 보고로, 세 차례의 결과를 나란히 견준다. 응답자 124명 가운데 109명(88%)이 P ≠ NP, 15명(12%)이 P = NP 라고 답했다. 2-6 의 수치 출처다. 다수 의견이 증명을 대신하지는 않는다는 점을 기억하고 읽는다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 세 설문의 비교표와 해당 절을 읽음.
    원문 주소 (www.cs.umd.edu)
  • 증명 주장원문 확인
    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)
  • 보조 자료원문 확인
    P versus NP problemWikipedia contributors · 2026영어 위키백과 (2026-10-05 확인)

    P 대 NP 문제를 다룬 영어 위키백과 문서다. 2-5 의 증명 주장 개관이, Woeginger 의 목록을 116건으로 센 다른 집계를 견주어 보이는 보조 자료로 썼다.

    확인:위키백과 문서를 직접 열어 해당 수치를 확인(2차 자료).
    원문 주소 (en.wikipedia.org)
  • 부분 결과서지만 확인
    Expressing combinatorial optimization problems by linear programsM. Yannakakis · 1991Journal of Computer and System Sciences 43(3), 441–466쪽 (1991) · 학회 발표 STOC 1988, 223–228쪽

    외판원 문제를 대칭적인 선형 계획으로 나타내려면 지수 크기가 필요함을 증명한 논문이다. 해밀턴 순환 문제를 다항 크기 선형 계획으로 적었다는 Swart 의 P = NP 주장을 끝낸 결과다. Woeginger 의 목록에서 연구자 사회가 옳다고 받아들인 유일한 논문으로 꼽히지만, 문제를 푼 것이 아니라 한 접근이 통할 수 없음을 보인 것이다. 2-5 의 증명 주장 개관이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Woeginger 의 목록 주석과 Aaronson 2017 4장의 각주 28 로 확인.
    원문 주소 (doi.org)DOI 10.1016/0022-0000(91)90024-y

하위 정보 0

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

아직 없습니다.