HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 1. P vs NP 문제는 무엇인가?
  3. 1-1 학술 자료

역사 — 문제는 어떻게 생겨났나

괴델이 폰 노이만에게 보낸 1956년 편지에서 Cobham 과 Edmonds 의 「다항 시간」, Cook·Karp·Levin 의 1971~1973년 논문, 2000년 밀레니엄 문제 지정까지, P 대 NP 문제가 모습을 갖춘 과정을 출처에서 확인한 사실만으로 따라간다.

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

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

괴델이 폰 노이만에게 보낸 1956년 편지에서 Cobham 과 Edmonds 의 「다항 시간」, Cook·Karp·Levin 의 1971~1973년 논문, 2000년 밀레니엄 문제 지정까지, P 대 NP 문제가 모습을 갖춘 과정을 출처에서 확인한 사실만으로 따라간다.

한눈에 보는 흐름

1930년부터 2005년까지의 연표 띠. 눈금 간격은 실제 햇수에 비례한다. 1936년 튜링 기계, 1953·1955·1956년 von Neumann 의 구별과 Nash 의 편지와 괴델의 편지, 1964~1965년 Cobham·Edmonds 의 다항 시간 기준과 Hartmanis–Stearns 의 틀, 1971·1972·1973년 Cook 의 발표와 Karp 의 21문제와 Levin 의 논문 게재, 2000년 밀레니엄 문제 지정이 표시되어 있다.
연표 띠. 1950년대 중반과 1964~1973년에 사건이 몰려 있다.
  1. Turing 이 튜링 기계를 내놓아 「계산할 수 있다」의 뜻이 정해진다
  2. von Neumann 이 다항 시간 알고리즘과 지수 시간 알고리즘을 구별한다
  3. Nash 가 미국 국가안보국에 보낸 편지에서 암호 해독의 어려움에 관한 추측을 적는다
  4. 괴델이 폰 노이만에게 편지를 보낸다
  5. Cobham 과 Edmonds 가 다항 시간을 「현실적으로 풀 수 있음」의 기준으로 제안한다
  6. Hartmanis 와 Stearns 가 단계 수로 문제를 분류하는 틀을 세운다
  7. Cook 이 NP-완전 문제의 존재를 발표한다
  8. Karp 가 21개 문제의 NP-완전성을 보인다
  9. Levin 의 논문이 소련에서 게재된다
  10. Clay 수학연구소가 밀레니엄 문제로 지정한다

무차별 탐색이라는 오래된 걱정

가능한 답을 모두 늘어놓고 하나씩 따져 보는 방법을 무차별 탐색(brute-force search)이라 한다. 원리로는 많은 문제가 이렇게 풀리지만, 따져 볼 것이 조금만 많아져도 쓸 수 없다. Sipser 의 1992년 개관에 따르면 이 현상을 특정 문제의 사정이 아니라 일반적인 현상으로 알아본 사람은 여럿이었고, 서로 모르는 채였다. 1950년대 소련의 연구자들은 이것을 「페레보르(perebor)」라 부르며 피할 수 있는지를 따졌다.

괴델의 1956년 편지

1956년 3월 20일, 프린스턴의 괴델은 병상의 폰 노이만에게 편지를 썼다. 안부 뒤에 수학 문제가 하나 나온다. 술어 논리의 식 F 와 자연수 n 이 주어졌을 때 F 에 길이 n 인 증명이 있는지를 판정하는 튜링 기계를 생각하고, 가장 좋은 기계가 쓰는 단계 수가 n 에 따라 얼마나 빨리 늘어나는지를 물은 것이다. 그 수가 n 이나 n² 에 비례하는 정도라면 어떻게 되는가에 대해 괴델은 이렇게 적었다(Sipser 의 논문 부록에 실린 영역).

this would have consequences of the greatest magnitude

이는 가장 큰 규모의 귀결을 낳을 것이다.

괴델이 폰 노이만에게 보낸 편지(1956년 3월 20일), Sipser 1992 부록의 영역

예/아니오로 답하는 물음에서는 수학자의 정신노동을 기계가 대신할 수 있게 된다는 뜻이었다. 괴델은 같은 편지에서 어떤 수가 소수인지 판정하는 데에는 단계를 얼마나 줄일 수 있는지도 궁금해했다. Aaronson 은 이 편지가 오늘날 P 대 NP 라 부르는 물음을 적은 것이라고 평가한다. Sipser 는 당시 암으로 투병하던 폰 노이만이 이 편지를 두고 생각했는지, 답장을 했는지 알려져 있지 않다고 적는다. 편지는 뒤늦게 알려졌다. Sipser 는 1992년 글에서 이를 「최근에 발견된」 편지라고 소개한다.

한 해 앞선 1955년에는 Nash 가 미국 국가안보국에 보낸 편지에서, 충분히 복잡한 암호라면 열쇠를 알아내는 계산의 길이가 열쇠 길이에 따라 지수적으로 늘어난다는 추측을 적었다. Aaronson 은 2017년 개관을 이 편지로 시작하면서 Nash 가 P 대 NP 문제를 사실상 정식화했다고 평가한다.

「다항 시간이면 풀 만하다」

1960년대에 두 사람이 서로 다른 길로 같은 기준에 이르렀다. Cobham 은 덧셈과 곱셈에 드는 단계 수가 자릿수의 다항식으로 한정된다는 데 주목해 그런 함수들의 클래스를 따로 다루자고 제안했고, 어떤 계산 기계로 정의해도 같은 클래스가 나온다는 점을 근거로 들었다. Edmonds 는 1965년 논문 「Paths, Trees, and Flowers」에서 그래프의 최대 매칭을 찾는 알고리즘을 내놓으면서, 유한한 방법이 있다는 것만으로는 모자라고, 수고가 그래프 크기에 따라 지수적으로가 아니라 다항식 정도로(그의 표현으로는 「대수적으로」) 늘어나는 「좋은(good)」 알고리즘이 있는지가 수학적으로 뜻있는 물음이라고 논했다.

같은 1965년에 Hartmanis 와 Stearns 는 튜링 기계가 쓰는 단계 수로 문제를 등급 매기는 이론을 세웠다. Arora 와 Barak 의 교과서에 따르면 「계산 복잡도(computational complexity)」라는 이름도 이 논문에서 왔다.

1971~1973년: 문제가 이름을 얻다

1971년 5월 미국 오하이오주 셰이커하이츠에서 열린 ACM 계산 이론 심포지엄(STOC)에서 Cook 이 「The Complexity of Theorem-Proving Procedures」를 발표했다. NP 의 모든 문제가 논리식 문제 하나로 환산된다는 결과였고, Sipser 는 Cook 이 이 논문에서 P 대 NP 추측을 처음으로 정확히 정식화했다고 적는다.

이듬해 Karp 가 그래프·정수·집합에 걸친 21개 문제가 모두 같은 처지임을 보였다. Cook 에 따르면 P 와 NP 라는 표기와 지금 표준이 된 NP-완전의 정의도 Karp 의 논문에서 왔다.

소련에서는 페레보르 문제를 다루던 흐름 속에서 Levin 이 Cook 과 Karp 를 모르는 채 「보편 탐색 문제」라는 개념에 이르렀다. 그의 두 쪽짜리 논문은 1972년 6월에 접수되어 1973년에 게재되었다. Clay 수학연구소는 Cook 과 Levin 이 1971년에 독립적으로 이 문제를 정식화했다고 적으며, SAT 가 NP-완전이라는 정리는 두 사람의 이름을 따 Cook–Levin 정리라 불린다. Cook 은 1982년에, Karp 는 1985년에 튜링상을 받았다.

2000년: 밀레니엄 문제

2000년 5월 24일 Clay 수학연구소는 파리의 콜레주 드 프랑스에서 일곱 개의 밀레니엄 문제를 발표했다. 상금 기금은 700만 달러, 문제마다 100만 달러다. P 대 NP 문제가 그 하나이고, 공식 문제 기술은 Cook 이 썼다.

Fortnow 는 2009년 개관의 첫머리에서 이 문제의 현황은 두 낱말로 족하다고 썼다. 「Still open(아직 열려 있다)」. Clay 의 문제 페이지에도 지금 「Unsolved」라고 적혀 있다.

출처

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

참고문헌 16

  • 개관원문 확인
    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
  • 역사원문 확인
    Letter to John von Neumann (20 March 1956)Kurt Gödel · 1956독일어 손편지(프린스턴, 1956년 3월 20일) · 해설과 핵심 대목의 영문 번역: Juris Hartmanis, 「Gödel, von Neumann and the P=?NP Problem」, Cornell University Computer Science TR 89-994 (1989년 4월) = Bulletin of the EATCS (1989년 6월) 101–107쪽 · 전문 영문 번역: Sipser 1992 의 부록 (Arthur S. Wensinger 옮김)

    괴델이 폰 노이만에게, 증명을 찾는 일을 기계가 얼마나 빨리 해낼 수 있는지 물은 편지다. P 대 NP 문제가 정식화되기 15년 전에 같은 물음의 핵심을 짚은 사료다. 연결한 Hartmanis 의 글(코넬 대학교 기술 보고서)은 편지가 쓰인 배경과 핵심 대목의 번역을 싣고 있고, 편지 전문의 영문 번역은 sipser-1992 의 부록에 있다. 문제의 역사에 관심 있는 모든 독자에게 권한다.

    확인:독일어 손편지가 아니라 영문 번역(Sipser 1992 의 부록, Lipton 의 「The Gödel Letter」 페이지)을 읽음.
    원문 주소 (ecommons.cornell.edu)
  • 보조 자료원문 확인
    The Gödel LetterRichard J. Lipton · 2026블로그 Gödel's Lost Letter and P=NP 의 고정 페이지 (2026-10-05 확인)

    괴델이 폰 노이만에게 보낸 1956년 편지를 소개하는, Lipton 블로그의 고정 페이지다. 편지의 영문 번역이 실려 있다. 1-1 의 역사 글이 편지의 날짜와 장소를, 「여러 얼굴」 글이 편지 본문을 확인하는 데 썼다.

    확인:2026-10-05 에 페이지를 직접 열어 편지 머리의 날짜·장소와 실린 영문 번역을 확인.
    원문 주소 (rjlipton.com)
  • 원전원문 확인
    The P versus NP ProblemStephen Cook · 2000Clay Mathematics Institute, Millennium Prize Problems 공식 문제 기술 (12쪽 PDF · 문서에 날짜 표기 없음 · Cook 의 홈페이지 출판 목록에 따르면 2000년 4월 작성·11월 개정 원고 · 밀레니엄 상 문제는 2000년 5월 24일 발표 · 현재 공개본은 2004년 문헌까지 인용하므로 그 뒤에 손본 판)

    Clay 수학연구소가 밀레니엄 상 문제로 내건 P 대 NP 문제의 공식 문제 기술이다. 문제의 정확한 진술, 역사와 중요성, 추측과 그것을 증명하려는 시도, 부록의 튜링 기계 정의로 이루어진 12쪽짜리 글이다. 「정확히 무엇을 증명해야 하는가」를 확인하려는 독자라면 누구나 가장 먼저 읽을 글이다.

    확인:공식 PDF 12쪽 전체를 내려받아 읽고, 인용한 다섯 문장을 원문과 글자 단위로 대조함.
    원문 주소 (www.claymath.org)
  • 원전서지만 확인
    The Intrinsic Computational Difficulty of FunctionsAlan Cobham · 1964Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, North-Holland, 24–30쪽 (1964년 학회 발표 · 논문집 간행 연도는 문헌에 따라 1964 또는 1965 — Sipser 1992 는 1964, Aaronson 2017 은 1965 로 적는다)

    덧셈과 곱셈처럼 단계 수가 자릿수의 다항식으로 한정되는 함수들을 따로 다루자고 제안해, 다항 시간이라는 기준의 뿌리가 된 글이다. Edmonds 의 1965년 논문과 함께 클래스 P 의 출발점으로 꼽힌다. 1-1 의 역사 글과 2-1 의 연표가 인용한다. 연결한 것은 Stephen Cook 의 누리집에 있는 사본이다.

    확인:Cook 누리집의 공개 사본을 열어 첫 쪽을 확인. 본문을 읽었다는 기록이 분명하지 않아 서지 확인으로 둠.
    원문 주소 (www.cs.toronto.edu)
  • 원전서지만 확인
    Paths, Trees, and FlowersJack Edmonds · 1965Canadian Journal of Mathematics 17, 449–467쪽 (1965)

    그래프의 최대 매칭을 찾는 알고리즘을 내놓으면서, 수고가 다항식 정도로만 늘어나는 「좋은」 알고리즘이 있는지가 뜻있는 물음이라고 논한 논문이다. Cobham 의 글과 함께, 다항 시간을 「현실적으로 풀 수 있음」의 기준으로 삼는 생각의 출발점이다. 1-1 의 역사 글과 2-1 의 연표가 인용한다.

    확인:서지는 DOI 등록 기록으로 확인. 본문은 Sipser 1992 의 부록에 실린 발췌로만 확인.
    원문 주소 (doi.org)DOI 10.4153/cjm-1965-045-4
  • 원전원문 확인
    On the computational complexity of algorithmsJuris Hartmanis, Richard E. Stearns · 1965Transactions of the American Mathematical Society 117 (1965), 285–306쪽

    계산에 드는 시간으로 문제를 분류하는 틀을 세우고 시간 위계 정리를 증명한 논문이다. 「계산 복잡도」라는 분야가 여기서 시작되었다. 대각선 논법으로 복잡도 종류를 가르는 방법의 뿌리를 보려는 독자에게 권한다. 미국수학회 누리집에 PDF 가 올라 있다.

    확인:미국수학회 누리집의 공개 PDF 를 열어 정리 6·정리 9 와 그 증명 요약을 읽음.
    원문 주소 (www.ams.org)
  • 원전원문 확인
    The complexity of theorem-proving proceduresStephen A. Cook · 1971STOC 1971 (Proceedings of the 3rd Annual ACM Symposium on Theory of Computing), 151–158쪽

    NP 의 모든 문제가 명제 논리식의 판정 문제로 환산됨을 보여 NP-완전 이론을 연 논문이다. 8쪽짜리 학회 논문으로, 다항 시간 환산의 개념과 오늘날 「SAT 는 NP-완전」이라 부르는 결과가 여기서 나온다. 용어와 표기(항진식 판정, 오라클을 쓰는 환산)가 지금과 달라서, 교과서로 개념을 익힌 뒤 원전을 확인하려는 독자에게 맞다. 연결한 것은 저자 누리집의 스캔본이다.

    확인:저자 누리집의 스캔본을 열어 요약 부분을 읽음.
    원문 주소 (www.cs.toronto.edu)
  • 원전서지만 확인
    Reducibility among Combinatorial ProblemsRichard M. Karp · 1972Complexity of Computer Computations (R. E. Miller, J. W. Thatcher, J. D. Bohlinger 엮음, Plenum Press, 1972), 85–103쪽

    서로 달라 보이는 조합 문제 21개가 모두 NP-완전임을 환산의 사슬로 보인 논문이다. 쿡의 결과가 한 문제에 그치지 않고 조합 최적화 전반에 걸친 현상임을 드러내 NP-완전성을 널리 알렸다. 클릭·정점 덮개·해밀턴 순환·배낭 문제 등으로 가는 환산을 직접 보고 싶은 독자에게 좋다. 게시자(Springer) 페이지이며 본문 열람에는 구독이 필요할 수 있다.

    확인:게시자 페이지와 DOI 등록 기록으로 서지를 확인. 1-1 의 NP-완전성 글은 주정리의 21문제 목록과 환산 그림을 이 논문에서 가져왔다고 적었으나, 본문을 어디서 열었는지는 기록에 없어 서지 확인으로 둠.
    원문 주소 (link.springer.com)
  • 원전서지만 확인
    Universal sequential search problemsLeonid A. Levin · 1973Problemy Peredachi Informatsii 9(3), 115–116쪽 (1973, 러시아어) · 영문 번역 Problems of Information Transmission 9(3), 265–266쪽

    쿡과 독립적으로, 여러 탐색 문제가 그런 종류의 문제 전체만큼 어려운 「보편」 문제임을 밝힌 두 쪽짜리 논문이다. 소련에서 러시아어로 발표된, 쿡–레빈 정리의 또 한쪽 원전이다. 내용보다 역사적 맥락을 확인하려는 독자에게 권한다. 연결한 Math-Net.Ru 페이지에 서지 사항과 러시아어 원문 PDF 가 있다.

    확인:Math-Net.Ru 의 서지·초록 페이지에서 접수일과 게재 서지를 확인. 러시아어 본문은 읽지 않았고 내용은 Cook 의 공식 문제 기술의 설명에 기댐.
    원문 주소 (www.mathnet.ru)
  • 개관원문 확인
    The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)

    P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 인용한 절들을 읽음.
    원문 주소 (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)
  • 보조 자료원문 확인
    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 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)
  • 보조 자료원문 확인
    Stephen Cook · Richard M. Karp (영어 위키백과 문서)Wikipedia contributors · 2026영어 위키백과 (2026-10-05 확인) · Karp 문서는 https://en.wikipedia.org/wiki/Richard_M._Karp

    Stephen Cook 과 Richard M. Karp 를 다룬 영어 위키백과 문서다. 1-1 의 역사 글이 두 사람의 튜링상 수상 연도(1982년, 1985년)를 확인하는 보조 자료로 썼다. ACM 의 수상자 페이지는 열지 못했다.

    확인:위키백과 문서를 직접 열어 해당 서술을 확인(2차 자료).
    원문 주소 (en.wikipedia.org)

하위 정보 0

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

아직 없습니다.