NP-완전성과 Cook–Levin 정리

다항 시간 환산으로 문제의 어려움을 견주는 법, NP-난해와 NP-완전의 정의, SAT 가 NP-완전이라는 Cook–Levin 정리의 뜻과 증명 얼개, Karp 의 21문제, 그리고 P 도 NP-완전도 아닐 수 있는 NP-중간 문제를 설명한다.

중급
관리자
2026-10-05 23:05
조회 0
AI 도움

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

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

환산 — 어려움을 견주는 자

두 문제 가운데 어느 쪽이 더 어려운지를 말하려면 자가 필요하다. 복잡도 이론의 자는 환산(reduction)이다.

언어 A 가 언어 B 로 다항 시간 환산된다는 것(A ≤_p B)은, 다항 시간에 계산되는 함수 f 가 있어서 모든 x 에 대해 「x ∈ A ⇔ f(x) ∈ B」가 성립한다는 뜻이다.

B 를 다항 시간에 푸는 알고리즘이 있으면 x 를 f(x) 로 바꿔 넘기는 것만으로 A 도 다항 시간에 풀린다. 그래서 A ≤_p B 는 「A 는 B 보다 어렵지 않다」로 읽는다. 환산은 이어 붙일 수 있다. A ≤_p B 이고 B ≤_p C 이면 A ≤_p C 이다.

NP-난해와 NP-완전

NP-난해: B 가 NP-난해(NP-hard)라는 것은 NP 의 모든 언어 A 에 대해 A ≤_p B 라는 뜻이다.
NP-완전: B 가 NP-완전(NP-complete)이라는 것은 B 가 NP-난해이면서 B 자신도 NP 에 속한다는 뜻이다.

NP-완전 문제는 NP 안에서 가장 어려운 문제다. 정의에서 세 가지가 곧바로 나오며, Cook 의 공식 기술은 이를 한 명제로 묶어 둔다.

첫째. A ≤_p B 이고 B ∈ P 이면 A ∈ P 이다.

둘째. A 가 NP-완전이고 B ∈ NP 이며 A ≤_p B 이면 B 도 NP-완전이다.

셋째. NP-완전 문제 하나가 P 에 속하면 P = NP 이다.

Cook, "The P versus NP Problem", 명제 1

Cook–Levin 정리

NP 에는 서로 닮지 않은 문제가 끝없이 들어 있다. 그 모두가 환산되는 문제가 하나라도 있다는 것부터가 당연하지 않다. Cook–Levin 정리는 그런 문제가 있고, 그것도 아주 단순한 문제라고 말한다.

정리. SAT 는 NP-완전이다. 3-SAT 도 NP-완전이다.

SAT: SAT(충족 가능성 문제, satisfiability)는 참·거짓 값을 갖는 변수들을 AND, OR, NOT 으로 엮은 식이 주어졌을 때 식 전체를 참으로 만드는 대입이 있는지를 묻는다.
3-SAT: 3-SAT 는 식의 꼴을 「리터럴 세 개를 OR 로 묶은 절들의 AND」로 제한한 것이다. 리터럴은 변수이거나 변수의 부정이다.

SAT 가 NP 에 속함은 쉽다. 참으로 만드는 대입이 증거다. 어려운 쪽은 NP 의 임의의 언어 L 을 SAT 로 환산하는 일이며, 핵심 생각은 「계산 과정을 논리식으로 적는다」이다.

L 이 NP 에 속하므로 다항 시간 검증자 V 가 있다. 입력 x 에 대해 「V 가 (x, u) 를 받아들이게 하는 증거 u 가 있다」를 논리식 F_x 로 옮기려 한다.
V 의 계산을 표로 그린다. 행은 시각, 열은 테이프의 칸이다. V 가 T 단계에 멈춘다면 표는 가로세로 T 쯤이고, 「시각 t 에 칸 i 에 기호 a 가 있다」, 「헤드가 거기 있고 상태가 q 다」 같은 사실 하나하나에 변수를 둔다.
표가 올바른 계산임을 조건으로 적는다. 첫 행은 x 와 아직 정해지지 않은 u 가 적힌 시작 상황이다. 각 행은 바로 앞 행에서 전이 함수대로 나온다. 마지막에는 수락 상태에 이른다.
둘째 조건이 식으로 적히는 까닭은 계산이 국소적이기 때문이다. 한 칸의 다음 내용은 앞 행에서 그 칸과 이웃 칸 몇 개만 보면 정해진다. 그래서 조건 전체가 작은 조각들의 AND 가 되고, 식의 크기는 T 의 다항식에 머문다.

검증자 V 의 계산을 그린 표. 행은 시각 0 부터 T 까지, 열은 테이프의 칸이다. 첫 행에는 입력 x 의 기호들과 아직 정해지지 않은 증거 u 의 칸이 있다. 시각 t 의 이웃한 세 칸이 시각 t+1 의 가운데 한 칸을 정한다는 것을 강조했고, 마지막 행은 수락 상태에 이른다. — 계산을 표로 그리면, 각 칸은 바로 앞 행의 이웃 몇 칸만 보고 정해진다. 그래서 「올바른 계산」이라는 조건을 작은 조각들의 AND 로 적을 수 있다.

이렇게 만든 F_x 는 x 가 L 에 속할 때, 그리고 그때에만 충족 가능하다. x 는 식에 박혀 있고 u 에 해당하는 변수만 자유롭게 남아서, 식을 참으로 만드는 대입이 곧 V 를 통과하는 증거이기 때문이다.

Cook 은 1971년 논문에서 이 결과를 발표했다. 논문의 요약은 다항 시간 비결정적 튜링 기계가 푸는 인식 문제는 모두 논리식이 항진식인지 판정하는 문제로 환산된다는 꼴로 적혀 있고, 환산도 신탁을 여러 번 부를 수 있는 꼴이었다. 소련의 Levin 은 독립적으로 「보편 탐색 문제」라는 개념을 세우고 충족 가능성을 포함한 여섯 개의 예를 들었다(1973년 게재). 위에서 쓴 함수 f 꼴의 환산을 표준으로 만든 사람은 Karp 다.

Karp 의 21문제

Cook–Levin 정리가 있으면 둘째 사실 덕분에 일이 쉬워진다. 새 문제 B 가 NP-완전임을 보이려면 이미 아는 NP-완전 문제 하나를 B 로 환산하면 된다. Karp 는 1972년 논문에서 SAT 를 뿌리로 삼아 환산을 나무처럼 이어 가며 21개 문제가 모두 완전함을 보였다.

왼쪽의 NP 의 모든 언어 L₁, L₂, L₃ … 에서 Cook–Levin 정리로 SAT 에 화살표가 모인다. SAT 에서 3-SAT 로, 3-SAT 에서 CLIQUE, NODE COVER, KNAPSACK, PARTITION, 3-DIMENSIONAL MATCHING, DIRECTED HAMILTON CIRCUIT, CHROMATIC NUMBER 같은 그 밖의 NP-완전 문제로 화살표가 이어진다. 화살표 A → B 는 A ≤p B 를 뜻한다. — 환산의 사슬. NP 의 모든 언어가 SAT 로 환산되므로, SAT(또는 3-SAT)를 환산해 넣을 수 있는 문제가 NP 에 속하면 그 문제도 NP-완전이다.

SATISFIABILITY, 0-1 INTEGER PROGRAMMING, CLIQUE, SET PACKING, NODE COVER, SET COVERING, FEEDBACK NODE SET, FEEDBACK ARC SET, DIRECTED HAMILTON CIRCUIT, UNDIRECTED HAMILTON CIRCUIT, SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE, CHROMATIC NUMBER, CLIQUE COVER, EXACT COVER, HITTING SET, STEINER TREE, 3-DIMENSIONAL MATCHING, KNAPSACK, JOB SEQUENCING, PARTITION, MAX CUT.

그래프, 정수, 집합, 일정 짜기에 걸친 이 목록은 NP-완전성이 논리학의 특수한 현상이 아님을 보여 주었다. Garey 와 Johnson 의 1979년 책은 부록에 NP-완전 문제 300개를 실었다.

「하나만 풀면 전부 풀린다」의 정확한 뜻

정확한 문장은 셋째 사실이다. 어떤 NP-완전 문제에 모든 입력에서 다항 시간 안에 끝나는 알고리즘이 있으면, NP 의 모든 문제에 그런 알고리즘이 있다. 거꾸로 NP 의 문제 하나라도 다항 시간에 풀 수 없다면 NP-완전 문제는 어느 것도 다항 시간에 풀 수 없다.

NP-중간 문제

NP 의 문제는 P 에 속하거나 NP-완전이거나 둘 중 하나일까. Ladner 는 1975년에 그렇지 않음을 보였다.

Ladner 정리. P ≠ NP 라면 NP 에 속하면서 P 에도 속하지 않고 NP-완전도 아닌 언어가 존재한다.

이런 문제를 NP-중간(NP-intermediate)이라 한다. 다만 증명이 만들어 내는 언어는 대각선 논법으로 짠 인공적인 것이다.

자연스러운 후보로 꼽히는 문제가 둘 있다.

인수분해. 대응하는 결정 문제는 NP 와 coNP 양쪽에 속한다. 이것이 NP-완전이라면 NP = coNP 가 되므로 NP-완전은 아닐 것으로 여겨진다. 다항 시간 알고리즘도 알려져 있지 않다.
그래프 동형. 두 그래프가 꼭짓점 이름만 바꾼 같은 그래프인지 묻는다. Babai 는 2015년에 준다항 시간, 곧 exp((log n)^O(1)) 시간 알고리즘을 발표했다. 이 문제가 NP-완전이라면 NP 전체가 준다항 시간에 풀리게 된다.

두 문제 모두 P 에 속하지 않는다는 것도, NP-완전이 아니라는 것도 증명된 바 없다. 후보 목록은 바뀌기도 한다. 소수 판정은 오랫동안 후보였으나 P 에 속함이 밝혀졌다.

출처

Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute 공식 문제 기술. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (환산과 NP-완전의 정의 3·4, 명제 1, SAT 환산의 얼개, 탐색과 판정, 인수분해 언어, Karp 와 Levin 에 대한 서술)
Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proc. 3rd ACM STOC, 1971, 151–158. 저자 공개 스캔본: https://www.cs.toronto.edu/~sacook/homepage/1971.pdf (요약 부분)
Richard M. Karp, "Reducibility among Combinatorial Problems", Complexity of Computer Computations, Plenum Press, 1972, 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9 (주정리의 21문제 목록과 환산 그림)
L. A. Levin, "Universal Sequential Search Problems", Problemy Peredachi Informatsii 9(3), 1973, 115–116. https://www.mathnet.ru/eng/ppi914
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 저자 공개 초고: https://theory.cs.princeton.edu/complexity/ (정의 2.7, 정리 2.10 과 증명의 「계산은 국소적」이라는 생각, 정리 3.4)
Richard E. Ladner, "On the Structure of Polynomial Time Reducibility", Journal of the ACM 22(1), 1975, 155–171. https://doi.org/10.1145/321864.321877 (본문은 열지 못해 정리의 진술은 Aaronson 과 Arora–Barak 으로 확인)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. (책은 열지 못함. Cook 의 공식 기술이 부록의 300개 목록을 언급)
Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (NP-중간 문제, 인수분해와 그래프 동형)
László Babai, "Graph Isomorphism in Quasipolynomial Time", arXiv:1512.03547. https://arxiv.org/abs/1512.03547

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

참고문헌 9

원전원문 확인
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 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)
교과서원문 확인
Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009
계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.
확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
원문 주소 (theory.cs.princeton.edu)
부분 결과서지만 확인
On the Structure of Polynomial Time ReducibilityRichard E. Ladner · 1975Journal of the ACM 22(1), 155–171쪽 (1975)
P ≠ NP 라면 P 에도 속하지 않고 NP-완전도 아닌 NP 문제가 반드시 있음을 증명한 논문이다. NP-중간이라는 개념의 근거가 되는 정리의 원전이다. 복잡도 이론 교과서에서 래드너의 정리를 먼저 읽고 원문을 찾는 독자에게 맞다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 정리의 진술은 Aaronson 2017 정리 5 와 Arora–Barak 공개 초고 정리 3.4 로 확인.
원문 주소 (doi.org)DOI 10.1145/321864.321877
교과서서지만 확인
Computers and Intractability: A Guide to the Theory of NP-CompletenessMichael R. Garey, David S. Johnson · 1979W. H. Freeman and Company, 1979 (ISBN 0-7167-1045-5)
NP-완전성 이론과 NP-완전 문제 목록을 집대성한 고전 교재다. 환산 증명을 짜는 법을 차근차근 가르치고, 부록에 NP-완전 문제를 분야별로 망라해 두어 지금도 사전처럼 쓰인다. 어떤 문제가 NP-완전인지 확인하거나 환산을 배우려는 독자에게 권한다. 합법적인 무료 공개본이 없어 책을 소개하는 위키백과 문서로 연결한다.
확인:책은 열지 못함. 서지와 부록(NP-완전 문제 목록)에 관한 서술은 Cook·Fortnow·Aaronson 의 글과 책을 소개하는 위키백과 문서로 확인.
원문 주소 (en.wikipedia.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)
부분 결과서지만 확인
Graph Isomorphism in Quasipolynomial TimeLászló Babai · 2016arXiv:1512.03547 (2015년 12월 제출, 2016년 1월 개정)
그래프 동형 문제를 준다항 시간에 푸는 알고리즘을 제시한 논문이다. 그래프 동형은 P 에 속한다고도 NP-완전이라고도 증명되지 않은 NP-중간 후보다. 1-1 의 NP-완전성 글이 이 후보의 현황으로 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 초록 페이지에서 제목·저자·제출 이력을 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv 1512.03547

하위 정보 0

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

아직 없습니다.