흔한 오해

NP 의 뜻, NP-완전과 「풀 수 없음」의 차이, 양자 컴퓨터가 할 수 있다고 알려진 일의 범위, 다항 시간과 지수 시간의 실제 빠르기, SAT 풀이기의 성공과 최악의 경우, 결정 불가능한 문제와의 구분까지 여섯 가지 오해를 문헌에 비추어 바로잡는다.

입문
관리자
2026-10-05 23:05
조회 0
AI 도움

검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

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

P 대 NP 문제는 널리 알려진 만큼 잘못 알려진 것도 많다. 자주 보이는 여섯 가지를 골랐다.

오해 1. 「NP 는 다항 시간이 아니라는 뜻이다」

NP 는 non-polynomial 의 줄임이 아니다. Cook 의 공식 문제 기술이 밝히듯 「비결정적 다항 시간(nondeterministic polynomial time)」의 줄임이며, 오늘날의 정의로는 「답이 예일 때 그 증거를 다항 시간에 확인할 수 있는 문제」의 클래스다.

따라서 NP 는 어려운 문제만 모은 것이 아니다. 다항 시간에 풀리는 문제는 모두 NP 에 속한다(P ⊆ NP). 두 수의 곱셈 결과가 맞는지 묻는 문제도 NP 에 속한다. NP 가운데 가장 어려운 문제를 가리키는 말은 따로 있고, 그것이 NP-완전이다.

오해 2. 「NP-완전 문제는 풀 수 없다」

풀 수 있다. NP 의 문제는 가능한 증거를 모두 시험해 보면 반드시 답이 나온다. 걸리는 시간이 지수적일 뿐이다(NP ⊆ EXP).

알려지지 않은 것은 「모든 입력에서 다항 시간 안에」 푸는 방법이다. 그런 방법이 없다는 것 또한 증명되지 않았다. 그것이 바로 P 대 NP 문제다. 그리고 NP-완전 문제의 개별 입력은 날마다 풀리고 있다. Fortnow 는 2009년 글에서 도시가 1만 개를 넘는 외판원 문제도 실제로 풀 수 있다고 적었다.

오해 3. 「양자 컴퓨터는 NP-완전 문제를 순식간에 푼다」

그런 알고리즘은 알려져 있지 않다.

Shor 가 1994년에 내놓은 알고리즘은 양자 컴퓨터가 있다면 인수분해와 이산 로그를 다항 시간에 푼다. 그런데 인수분해는 NP-완전 문제로 여겨지지 않는다. Fortnow 는 Shor 의 알고리즘이 수의 대수적 구조에 크게 기대며, 알려진 NP-완전 문제에서는 그런 구조가 보이지 않는다고 설명한다.
Bennett·Bernstein·Brassard·Vazirani 는 1997년 논문에서, 무작위로 고른 신탁에 대해서는 확률 1 로 양자 튜링 기계가 NP 를 o(2^n/2) 시간에 풀 수 없음을 증명했다. 문제의 구조를 쓰지 않고 2ⁿ 개의 후보를 뒤지는 방식으로는 제곱근만큼 빨라지는 것이 한계라는 뜻이다. Grover 의 1996년 알고리즘이 정확히 그만큼, 곧 N 개 가운데 하나를 √N 번쯤에 찾는다.

제곱근 가속으로는 2ⁿ 이 2^n/2 이 될 뿐 여전히 지수적이다. Aaronson 은 지금까지 아는 한 양자 컴퓨터로도 3-SAT 에는 지수 시간이 든다고 정리한다.

오해 4. 「다항 시간은 빠르고 지수 시간은 느리다」

대체로는 맞지만 언제나 그렇지는 않다. 이 구분은 입력이 한없이 커질 때의 추세에 관한 것이다.

Cook 은 n¹⁰⁰ 단계가 드는 프로그램이 n = 10 에서도 돌릴 수 없다는 예를 든다. 다항 시간임은 증명되었는데 숨은 상수가 너무 커서 쓸 수 없는 알고리즘도 실제로 있다(그래프 마이너 이론의 결과들).
Aaronson 은 반대쪽 예를 든다. 현실적인 크기의 n 에서는 1.0000001ⁿ 단계가 n¹⁰⁰⁰ 단계보다 낫다.

그런데도 다항 시간을 기준으로 삼는 까닭이 있다. Aaronson 에 따르면 경험적으로 P 에 속하는 중요한 문제는 대부분 n, n², n³ 정도의 시간에 풀리고, P 밖이라고 여겨지는 중요한 문제는 대부분 알려진 알고리즘으로 cⁿ 꼴의 시간이 든다. P 대 NP 는 실용 속도에 관한 물음이 아니라, 그보다 먼저 답해야 할 굵은 경계에 관한 물음이다.

오해 5. 「SAT 풀이기가 잘 푸니 SAT 는 사실상 쉬운 문제다」

SAT 풀이기(SAT solver)의 성공은 사실이다. Fortnow 는 경연에서 풀이기들이 변수 100만 개짜리 식의 충족 가능성을 가려내는 일이 흔하다고 적는다. 소프트웨어 검증 같은 실제 작업에서 나오는 식은 최악의 경우보다 훨씬 쉬울 수 있고, 풀이기의 휴리스틱은 그런 입력에서 힘을 낸다.

NP-완전성은 다른 것을 말한다. 「어떤 입력이 오더라도」 다항 시간 안에 끝난다고 보장하는 알고리즘이 있는가이다. Fortnow 는 같은 글에서 일반적인 식에 대해서는 사실상 모든 경우를 뒤지는 것보다 나은 알고리즘을 알지 못한다고도 적는다. 잘 풀리는 입력이 많다는 것은 P = NP 의 증거가 아니고, 최악의 경우가 어렵다는 것은 실전에서 못 쓴다는 뜻이 아니다. 둘은 서로 다른 물음에 대한 답이다.

오해 6. 「NP-완전 문제는 컴퓨터로 못 푸는 문제다」

컴퓨터로 못 푸는 문제는 따로 있다. 결정 불가능(undecidable)한 문제다. 대표적인 예가 정지 문제(Halting Problem)로, 주어진 프로그램이 멈추는지를 모든 경우에 옳게 판정하는 알고리즘은 시간을 아무리 주어도 존재하지 않는다. Turing 이 1936년 논문에서 대각선 논법으로 보인 사실이다.

왼쪽 큰 상자 「결정 가능한 문제 — 시간만 충분하면 반드시 답이 나온다」 안에 EXP, NP, P 가 차례로 안에 든 타원이 있다. EXP 에는 「지수 시간이면 풀린다 · NP ⊆ EXP」, NP 에는 「NP-완전 문제도 여기에 속한다」라고 적혀 있다. 오른쪽 점선 상자 「결정 불가능한 문제 — 시간을 아무리 주어도 판정하는 알고리즘이 없다」 안에 정지 문제가 있다(Turing, 1936, 대각선 논법으로 증명). — NP-완전 문제는 결정 가능한 쪽에 있다. 컴퓨터로 못 푸는 문제는 정지 문제 같은 결정 불가능한 문제다. 영역의 크기와 경계는 포함 관계만 나타낸다.

NP 의 문제는 모두 결정 가능하다. 오해 2 에서 본 대로 시간만 충분하면 반드시 답이 나온다. P 대 NP 는 「풀 수 있는가」가 아니라 「풀 수 있는 문제 가운데 어디까지가 효율적으로 풀리는가」를 묻는다.

한눈에

오해	실제
NP = 다항 시간이 아님	NP = 비결정적 다항 시간. P 의 문제도 모두 NP 에 속한다
NP-완전 = 풀 수 없음	지수 시간이면 풀린다. 다항 시간 해법이 있는지 모를 뿐이다
양자 컴퓨터가 NP-완전 문제를 푼다	알려진 바 없다. Shor 는 인수분해, 일반 탐색은 제곱근 가속까지
다항 = 빠름, 지수 = 느림	큰 입력에서의 추세다. 예외가 있다
SAT 풀이기가 잘 푼다 = 쉬운 문제	실전 입력과 최악의 경우는 다른 물음이다
NP-완전 = 컴퓨터로 못 푸는 문제	못 푸는 것은 결정 불가능한 문제다. NP 는 모두 결정 가능하다

출처

Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute 공식 문제 기술. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (NP 라는 이름의 뜻, n^100 과 그래프 마이너의 예, 정지 문제와 Turing 의 대각선 논법, 인수분해의 지위)
Lance Fortnow, "The Status of the P versus NP Problem", Communications of the ACM 52(9), 2009, 78–86. 저자 공개본: https://lance.fortnow.com/papers/files/pnp-cacm.pdf (5절: 외판원 문제와 SAT 풀이기, 일반 식에 대한 한계 · 8절: 양자 컴퓨터)
Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (1.2.1절: 점근적 기준에 대한 반론과 답 · 5.5절: 양자 알고리즘)
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 저자 공개 초고: https://theory.cs.princeton.edu/complexity/ (NP 의 문제는 증거를 모두 시험해 지수 시간에 풀린다는 주장 2.3)
Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", Proc. 35th FOCS, 1994, 124–134. 확장판: SIAM Journal on Computing 26(5), 1997, 1484–1509, https://arxiv.org/abs/quant-ph/9508027
C. H. Bennett, E. Bernstein, G. Brassard, U. Vazirani, "Strengths and Weaknesses of Quantum Computing", SIAM Journal on Computing 26(5), 1997, 1510–1523. https://arxiv.org/abs/quant-ph/9701001
Lov K. Grover, "A Fast Quantum Mechanical Algorithm for Database Search", Proc. 28th ACM STOC, 1996, 212–219. https://arxiv.org/abs/quant-ph/9605043

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

참고문헌 7

원전원문 확인
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 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)
부분 결과서지만 확인
Algorithms for quantum computation: discrete logarithms and factoringPeter W. Shor · 1994FOCS 1994 (Proceedings 35th Annual Symposium on Foundations of Computer Science), 124–134쪽 · 학술지판 「Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer」, SIAM Journal on Computing 26(5), 1484–1509쪽 (1997)
양자 컴퓨터로 인수분해와 이산 로그를 다항 시간에 풀 수 있음을 보인 논문이다. 인수분해가 BQP 에 속함을 보인 결과다. 인수분해는 NP-완전으로 여겨지지 않으므로, 이것이 양자 컴퓨터로 NP 문제를 모두 푼다는 뜻은 아니다. 연결한 것은 학술지판(1997)의 arXiv 공개본이다.
확인:학술지판의 arXiv 초록 페이지에서 제목·저자·초록을 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv quant-ph/9508027
부분 결과서지만 확인
Strengths and Weaknesses of Quantum ComputingCharles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani · 1997SIAM Journal on Computing 26(5), 1510–1523쪽 (1997)
양자 컴퓨터도 구조를 쓰지 않는 탐색에서는 제곱근만큼의 가속이 한계임을 보인 논문이다. 무작위 오라클에 상대적으로는 양자 컴퓨터도 NP 문제를 2^(n/2) 보다 본질적으로 빨리 풀 수 없음을 보여, 「양자 컴퓨터가 NP-완전 문제를 쉽게 푼다」는 기대에 선을 긋는다. 양자 계산과 P 대 NP 의 관계가 궁금한 독자에게 권한다. arXiv 공개본으로 연결한다.
확인:arXiv 초록 페이지에서 제목·저자·초록을 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv quant-ph/9701001
부분 결과서지만 확인
A Fast Quantum Mechanical Algorithm for Database SearchLov K. Grover · 1996STOC 1996 (Proceedings of the 28th Annual ACM Symposium on Theory of Computing), 212–219쪽
N 개의 후보 가운데 하나를 √N 번쯤의 질의로 찾는 양자 탐색 알고리즘을 제시한 논문이다. 구조를 쓰지 않는 탐색에서 양자 컴퓨터가 주는 가속이 제곱근 수준임을 보여 주는 알고리즘으로, 1-1 의 흔한 오해 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 초록 페이지에서 제목·저자·초록을 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv quant-ph/9605043

하위 정보 0

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

아직 없습니다.