왜 필요한가 — “풀 수 있다”와 “빨리 풀 수 있다”는 다르다

지금까지 배운 정렬·탐색·그래프 알고리즘은 모두 입력 크기 n에 대해 다항식 형태(O(n), O(n log n), O(n^2) 등)의 시간이 걸리는, 효율적으로 풀리는 문제였다. 그런데 세상의 모든 문제가 이렇게 효율적으로 풀리는 것은 아니다. 예를 들어 “여러 도시를 한 번씩만 방문하고 출발지로 돌아오는 최단 경로를 찾아라”(외판원 문제, TSP)는 도시 수가 늘어날수록 답을 구하는 데 걸리는 시간이 폭발적으로 늘어나며, 지금까지 이 문제를 다항 시간에 정확히 푸는 방법은 발견되지 않았다.

계산 복잡도 이론(computational complexity theory)은 “어떤 문제가 원리적으로 효율적으로 풀릴 수 있는가”를 다루는 분야다. 독학사 4단계 시험에서는 이 분야의 증명 테크닉까지 요구하지는 않지만, P·NP·NP-완전·NP-난해라는 용어의 정의와 서로의 관계를 정확히 구분하는 개념 문제가 꾸준히 출제된다.

쉽게 말하면: 지금까지는 “이 문제를 어떻게 빨리 풀까”를 배웠다면, 이 편은 “이 문제가 애초에 빨리 풀리는 부류에 속하는가”를 판별하는 틀을 배우는 것이다.

결정 문제와 다항시간 알고리즘

계산 복잡도 이론은 편의상 문제를 결정 문제(decision problem, 답이 “예” 또는 “아니오”로만 나오는 문제) 형태로 다룬다. 예를 들어 “이 그래프에 크기 k 이상의 정점 커버가 존재하는가?”처럼 원래 최적화 문제(정점 커버의 최소 크기를 구하라)를 “예/아니오로 답할 수 있는 질문”으로 바꿔서 다룬다. 이렇게 바꾸는 이유는 최적화 문제와 결정 문제의 어려움이 본질적으로 같은 경우가 많아서, 결정 문제 형태로 이론을 통일해 다루는 것이 수학적으로 더 다루기 쉽기 때문이다.

다항시간 알고리즘(polynomial-time algorithm)은 입력 크기 n에 대해 실행 시간이 O(n^k)(k는 어떤 고정된 상수) 형태로 표현되는 알고리즘이다. 이 과목에서 배운 정렬(O(n log n)), 그래프 순회(O(V+E)), 최단경로(O(V^2)나 O(E log V)) 알고리즘은 모두 다항시간 알고리즘이다. 계산 복잡도 이론에서는 관례적으로 다항시간 알고리즘이 존재하는 문제를 “효율적으로 풀 수 있는 문제”로 취급한다.

자주 틀리는 점: O(n^100)도 형식적으로는 다항시간이지만 실제로는 매우 느리고, O(1.0001^n)도 지수 함수이지만 n이 작을 때는 다항시간 알고리즘보다 빠를 수 있다. 계산 복잡도 이론의 “효율적”이라는 말은 실제 체감 속도가 아니라 입력이 커질 때의 이론적 증가 추세를 기준으로 한 정의라는 점을 구분해야 한다.

P 클래스 — 다항시간에 풀리는 문제들의 모임

P 클래스(class P, Polynomial의 앞 글자를 딴 이름)는 결정론적 알고리즘으로 다항시간 안에 풀 수 있는 결정 문제들의 집합이다. 여기서 “결정론적”(deterministic)이란 같은 입력에 대해 항상 같은 절차를 밟아 같은 결과를 내는, 우리가 지금까지 다룬 보통의 알고리즘을 말한다.

• 예: “정렬된 배열에서 특정 값이 존재하는가?”(이진 탐색, O(log n)), “그래프에 특정 두 정점을 잇는 경로가 존재하는가?”(BFS/DFS, O(V+E)), “그래프가 이분 그래프인가?”(BFS로 색칠, O(V+E)) 등은 모두 P에 속한다.

NP 클래스 — “검증은 빠르게 되는” 문제들의 모임

NP 클래스(class NP, Nondeterministic Polynomial time의 줄임말)는 어떤 후보 답(증거, certificate)이 주어졌을 때, 그 답이 맞는지를 다항시간 안에 검증할 수 있는 결정 문제들의 집합이다. 여기서 핵심은 “답을 찾는 것”이 아니라 “주어진 답이 맞는지 확인하는 것”이 빠르다는 정의라는 점이다.

예를 들어 해밀턴 사이클 문제(“이 그래프에 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 사이클이 존재하는가?”)를 생각해 보자. 이 문제의 답(사이클)을 처음부터 찾으려면 가능한 모든 정점 순서를 다 시도해야 할 수도 있어 매우 오래 걸릴 수 있다. 하지만 누군가 “이 순서가 해밀턴 사이클입니다”라고 후보를 하나 제시하면, 그 순서가 정말로 모든 정점을 한 번씩 방문하고 인접한 정점끼리만 연결되어 있는지는 정점 개수만큼만 확인하면 되므로 O(V)(다항시간)에 검증할 수 있다. 이렇게 “검증이 빠른” 성질을 가진 문제가 NP에 속한다.

자주 틀리는 점(가장 흔한 오개념): NP를 “Not Polynomial”(다항시간이 아니다)의 줄임말로 잘못 아는 경우가 많다. 실제로는 Nondeterministic Polynomial(비결정론적 다항시간)의 줄임말이며, “답을 검증하는 데 다항시간이 걸린다”는 뜻이다. 또한 P에 속하는 모든 문제는 NP에도 속한다(P ⊆ NP). 다항시간에 스스로 풀 수 있는 문제라면, 답을 검증하는 것도 당연히 다항시간 안에 가능하기 때문이다(그냥 처음부터 다시 풀어서 확인하면 된다).

이 그림은 관계의 방향을 보여주기 위한 것으로, 실제로는 P와 NP-완전이 서로 겹치는지(P = NP인지)는 아직 증명되지 않은 미해결 문제다. 대부분의 학자들은 P ≠ NP(P가 NP의 진부분집합)일 것이라고 추측하지만, 2026년 현재까지 수학적으로 증명되지 않았다.

NP-완전과 NP-난해 — 가장 어려운 문제들

NP-완전(NP-complete)은 NP 클래스에 속한 문제들 중에서도 가장 어려운 문제들의 부류다. 정확한 정의는 두 조건을 모두 만족하는 문제다.

1. 그 문제가 NP에 속한다(답을 다항시간에 검증할 수 있다).
2. NP에 속한 다른 모든 문제를 이 문제로 다항시간 안에 환원(reduction)할 수 있다.

NP-난해(NP-hard)는 조건 2만 만족하는 문제들의 부류다. 즉 NP의 다른 모든 문제를 이 문제로 환원할 수 있을 만큼 어렵지만, 정작 자기 자신은 NP에 속하는지(답을 다항시간에 검증할 수 있는지)는 따지지 않는다. 그래서 NP-난해 문제 중에는 결정 문제가 아니거나, NP보다 더 어려운 문제도 포함될 수 있다.

쉽게 말하면: NP-완전은 “NP 세계 안에서 가장 어려운 문제”이고, NP-난해는 “적어도 NP 세계에서 가장 어려운 문제만큼 어려운 문제”다. NP-완전은 항상 NP-난해에 속하지만, NP-난해라고 해서 항상 NP-완전인 것은 아니다.

다항시간 환원 — 문제 사이의 난이도를 비교하는 도구

환원(reduction)은 “문제 A를 문제 B로 바꿔서 풀 수 있다”는 것을 보이는 절차다. 다항시간 환원(polynomial-time reduction)은 문제 A의 어떤 입력이든 다항시간 안에 문제 B의 입력으로 변환할 수 있고, 그렇게 변환된 문제 B를 풀면 원래 문제 A의 답도 알 수 있다는 뜻이다. 이를 기호로 A ≤p B(A가 B로 다항시간 환원된다)라고 쓴다.

환원이 중요한 이유는 다음 두 가지 추론을 가능하게 하기 때문이다.

• 만약 A ≤p B이고 B가 다항시간에 풀린다면, A도 다항시간에 풀린다(B를 푸는 다항시간 알고리즘에 A를 B로 바꾸는 변환만 추가하면 되므로).
• 반대로 A ≤p B이고 A가 어렵다고(NP-완전이라고) 이미 알려져 있다면, B도 최소한 A만큼 어렵다는 것을 보일 수 있다.

이 두 번째 추론이 바로 새로운 문제가 NP-완전임을 증명하는 표준적인 방법이다. 이미 NP-완전으로 알려진 문제를 새 문제로 환원할 수 있음을 보이면, 새 문제도 NP-완전이라는 결론을 얻는다.

역사적으로 이 사슬의 첫 출발점이 된 문제가 SAT(불 만족성 문제, Boolean satisfiability problem)로, “주어진 불 논리식을 참으로 만드는 변수 할당이 존재하는가?”를 묻는 문제다. 쿡-레빈 정리(Cook-Levin theorem)는 SAT가 NP-완전임을 최초로 증명한 정리로, 이후 수많은 문제들이 “SAT를 이 문제로 환원할 수 있다”는 방식으로 줄줄이 NP-완전임이 밝혀졌다.

대표적인 NP-완전 문제

독학사 시험에서는 각 문제의 증명 과정보다 문제 이름과 정의를 알아보는 수준이 요구된다. 자주 등장하는 대표 NP-완전 문제는 다음과 같다.

자주 틀리는 점: 그래프 색칠 문제에서 “2색으로 칠할 수 있는가”(이분 그래프 판별)는 P에 속하는 문제(BFS/DFS로 다항시간에 판별 가능)이지만, “3색 이상으로 칠할 수 있는가”는 NP-완전이다. 이처럼 문제의 조건을 살짝 바꾸는 것만으로 난이도 클래스가 완전히 달라질 수 있으므로, “그래프 색칠은 무조건 NP-완전”이라고 단순 암기하면 함정 문제에서 틀리기 쉽다.

자주 나오는 개념 판별·오개념 정리

• NP는 “다항시간에 풀 수 없는 문제”가 아니다. NP는 “답을 검증하는 데 다항시간이 걸리는 문제”의 집합이며, P에 속한 문제도 당연히 NP에 속한다.
• NP-완전 문제가 다항시간에 풀 수 없다고 증명된 것은 아니다. P = NP인지는 미해결 문제이며, 만약 언젠가 어떤 NP-완전 문제 하나라도 다항시간 알고리즘이 발견되면 환원 관계에 의해 모든 NP 문제가 다항시간에 풀린다는 것이 증명된다. 이것이 P vs NP 문제가 중요한 이유다.
• NP-난해는 결정 문제가 아닐 수도 있다. 예를 들어 “이 그래프의 최적 정점 커버는 몇 개인가”처럼 숫자를 직접 구하는 최적화 문제도 NP-난해라고 부를 수 있지만, 결정 문제가 아니므로 NP에 속하는지는 별도로 따지지 않는다.
• 환원의 방향에 주의한다. A ≤p B는 “A를 B로 바꿔 풀 수 있다”는 뜻이며, 이는 “B가 A보다 어렵거나 같다”는 의미다. 방향을 거꾸로 읽으면 추론이 뒤집힌다.

핵심 정리

• 결정 문제는 답이 “예/아니오”로만 나오는 문제 형태이며, 다항시간 알고리즘은 O(n^k) 형태로 시간이 걸리는 알고리즘이다.
• P는 다항시간에 직접 풀 수 있는 문제, NP는 답을 다항시간에 검증할 수 있는 문제의 집합이며 P ⊆ NP가 성립한다.
• NP-완전은 NP에 속하면서 NP의 다른 모든 문제를 다항시간 환원으로 받아낼 수 있는, NP 안에서 가장 어려운 문제다. NP-난해는 그 환원 조건만 만족하고 NP 소속 여부는 따지지 않는 더 넓은 개념이다.
• 다항시간 환원(A ≤p B)은 새로운 문제가 NP-완전임을 증명하는 표준 도구이며, SAT가 쿡-레빈 정리로 최초의 NP-완전 문제임이 증명된 이후 여러 문제가 연쇄적으로 NP-완전임이 밝혀졌다.
• P = NP인지는 아직 증명되지 않은 미해결 문제이며, NP는 “Not Polynomial”이 아니라 “Nondeterministic Polynomial”의 줄임말이라는 점이 시험에서 자주 나오는 함정이다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 학습정보  — 계산 복잡도 개요 항목의 출제 수준(정의·판별 중심) 확인.
• NIST, Dictionary of Algorithms and Data Structures — NP-complete  — NP-완전·NP-난해 등 계산 복잡도 용어의 표준 정의 참고.