NP 완전 문제는 ‘정답을 확인하는 일’과 ‘정답을 직접 찾는 일’ 사이에 큰 차이가 생기는 계산 문제다. 핵심은 특정 문제 하나가 어렵다는 데 그치지 않고, NP에 속한 모든 문제를 그 문제로 바꿔 풀 수 있다는 구조에 있다.
📌 핵심 5줄 요약
1. NP는 답이 주어졌을 때 그 답이 맞는지 다항 시간 안에 검증할 수 있는 문제들의 범주다.
2. NP 완전 문제는 NP에 속하면서 NP의 모든 문제를 다항 시간에 환원할 수 있는 문제다.
3. NP 완전 문제라고 해서 모든 입력에서 반드시 느리거나 절대 풀 수 없다는 뜻은 아니다.
4. NP 완전 문제 하나라도 다항 시간 알고리즘으로 풀리면 P=NP가 된다.
5. 현재 P와 NP가 같은지 다른지는 증명되지 않은 대표적인 미해결 문제다.
📌 목차
01 | NP 완전 문제의 뜻
02 | P와 NP의 차이
03 | ‘빠르다’고 말하는 기준
04 | 검증과 탐색의 차이
05 | NP 완전의 두 가지 조건
06 | 다항 시간 환원이란
07 | 대표 사례: SAT와 3-SAT
08 | 대표 사례: 해밀턴 경로와 그래프 문제
09 | 대표 사례: 배낭 문제와 일정 계획
10 | NP-hard와 NP-complete의 차이
11 | P=NP라면 달라지는 점
12 | 실제 프로그램은 어떻게 다루는가
13 | 흔한 오해와 주의점
14 | 공부할 때 기억할 구조
01 | NP 완전 문제의 뜻
NP 완전 문제는 크게 두 조건을 동시에 만족한다. 첫째, 어떤 해답이 주어졌을 때 그 해답이 조건을 만족하는지 다항 시간 안에 확인할 수 있어야 한다. 둘째, NP에 속하는 모든 문제를 해당 문제로 효율적으로 변환할 수 있어야 한다.
여기서 ‘완전’은 답이 완벽하다는 뜻이 아니다. NP라는 범주 안에서 다른 문제들의 계산 난이도를 대표할 만큼 어렵다는 의미다.
02 | P와 NP의 차이
P는 입력 크기 n에 대해 다항식 시간 안에 해답을 계산할 수 있는 결정 문제의 집합이다. 반면 NP는 해답 후보가 주어졌을 때 그 후보가 맞는지 다항식 시간 안에 검증할 수 있는 문제의 집합으로 설명할 수 있다.
따라서 P에 속하는 문제는 일반적으로 NP에도 속한다. 정답을 빠르게 찾을 수 있다면, 찾은 정답을 빠르게 확인하는 것도 가능하기 때문이다. 그러나 NP에 속한다고 해서 정답을 빠르게 찾는 방법이 알려져 있다는 뜻은 아니다.
03 | ‘빠르다’고 말하는 기준
계산 복잡도에서 빠르다는 표현은 보통 입력 길이에 대한 다항식 시간으로 정의한다. 예를 들어 n, n², n³처럼 입력 크기의 고정된 거듭제곱에 비례하는 시간은 다항식 시간으로 본다.
반대로 2ⁿ, 3ⁿ, n!처럼 입력이 조금만 커져도 계산량이 급격히 증가하는 함수는 일반적으로 다루기 어렵다. 물론 실제 실행 시간은 하드웨어와 구현에 따라 달라지지만, 복잡도 이론은 특정 컴퓨터보다 문제의 규모가 커질 때 증가 양상을 분석한다.
04 | 검증과 탐색의 차이
NP의 직관을 이해하려면 ‘후보 해답 확인’과 ‘해답 찾기’를 구분해야 한다.
간단한 예시
여러 사람 중 서로 사이가 좋지 않은 사람을 피하면서 정해진 인원을 선발한다고 하자. 누군가 선발 명단을 제출하면 조건을 위반한 쌍이 있는지 확인하는 일은 비교적 간단하다. 하지만 조건을 만족하는 명단을 처음부터 찾으려면 가능한 조합을 넓게 탐색해야 할 수 있다.
이처럼 답을 보여주면 빠르게 검증할 수 있지만, 답을 만들어내는 과정은 어려울 수 있다는 점이 NP의 핵심 직관이다.
05 | NP 완전의 두 가지 조건
어떤 문제가 NP 완전인지 판단할 때는 다음 두 조건을 확인한다.
| 조건 | 확인할 내용 |
|---|---|
| NP에 속함 | 후보 해답이 주어졌을 때 정답 여부를 다항 시간 안에 검증할 수 있어야 한다. |
| NP-hard임 | NP에 속한 모든 문제를 다항 시간 환원으로 해당 문제에 연결할 수 있어야 한다. |
둘 중 하나만 만족하면 NP 완전이라고 부를 수 없다. NP에 속하지 않지만 NP-hard인 문제도 있고, NP에 속하지만 아직 NP-hard임이 밝혀지지 않은 문제도 있다.
06 | 다항 시간 환원이란
환원은 한 문제를 다른 문제의 형태로 바꾸는 방법이다. 문제 A를 문제 B로 다항 시간 안에 변환할 수 있다면, B를 풀 수 있는 알고리즘을 이용해 A도 풀 수 있다.
예를 들어 A의 입력을 B의 입력으로 바꾸는 과정이 빠르고, B의 정답을 이용해 A의 정답을 해석할 수 있다면 A는 B보다 본질적으로 어렵지 않다고 볼 수 있다. NP 완전 문제는 이런 환원을 통해 NP 전체의 난이도를 한 문제 안에 담는다.
그래서 NP 완전 문제 중 하나에 다항 시간 알고리즘이 발견되면, 환원을 이용해 다른 NP 문제들도 다항 시간에 풀 수 있게 된다.
07 | 대표 사례: SAT와 3-SAT
SAT는 논리식에 포함된 변수에 참과 거짓을 배정해 전체 논리식이 참이 되도록 만들 수 있는지 묻는 문제다. 예를 들어 여러 조건을 동시에 만족하는 변수 배정이 존재하는지 판단한다.
3-SAT는 각 절이 최대 세 개의 리터럴로 구성된 형태의 SAT 문제다. 단순한 논리식처럼 보이지만, 다양한 조합 문제를 3-SAT 형태로 바꿀 수 있어 NP 완전성의 대표적인 출발점으로 활용된다.
중요한 점은 SAT의 모든 입력이 실제로 느리다는 뜻이 아니라, 일반적인 입력에 대해 알려진 다항 시간 알고리즘이 없고 문제 구조에 따라 계산량이 크게 달라질 수 있다는 점이다.
08 | 대표 사례: 해밀턴 경로와 그래프 문제
해밀턴 경로 문제는 그래프의 모든 정점을 중복 없이 방문하는 경로가 존재하는지 묻는다. 경로 하나가 주어지면 각 정점을 빠짐없이 방문했는지, 간선이 실제로 연결되어 있는지 확인할 수 있다.
그래프의 정점과 간선이 늘어나면 가능한 경로의 수가 빠르게 증가할 수 있다. 이 때문에 경로를 하나씩 모두 시험하는 방식은 큰 입력에서 비효율적일 수 있다. 해밀턴 경로는 ‘후보 해답은 검증하기 쉽지만 해답 탐색은 어려울 수 있다’는 NP의 특징을 잘 보여준다.
09 | 대표 사례: 배낭 문제와 일정 계획
배낭 문제는 각 물건의 가치와 무게가 주어졌을 때, 제한된 무게 안에서 목표 가치 이상을 얻을 수 있는지 판단하는 문제다. 선택한 물건 목록이 주어지면 전체 무게와 가치를 합산해 조건을 확인할 수 있다.
일정 계획, 작업 배치, 자원 배분처럼 선택 가능한 조합이 많은 문제도 비슷한 구조를 가질 수 있다. 다만 실무에서 사용되는 모든 일정 문제나 배낭 문제의 변형이 자동으로 NP 완전인 것은 아니다. 입력 형식과 제약 조건에 따라 난이도가 달라진다.
10 | NP-hard와 NP-complete의 차이
NP-hard는 적어도 NP의 모든 문제만큼 어렵다는 뜻이다. NP-hard 문제는 NP에 속할 필요가 없으므로, 후보 해답을 다항 시간에 검증할 수 없는 문제도 포함될 수 있다.
반면 NP-complete는 반드시 NP에 속해야 한다. 따라서 다음처럼 기억하면 된다.
| 구분 | 핵심 의미 |
|---|---|
| NP | 후보 해답을 다항 시간에 검증할 수 있는 문제 집합 |
| NP-hard | NP의 모든 문제 이상으로 어렵다고 볼 수 있는 문제 |
| NP-complete | NP에 속하면서 NP-hard인 문제 |
11 | P=NP라면 달라지는 점
P=NP는 빠르게 검증할 수 있는 모든 문제를 빠르게 찾을 수도 있는지를 묻는 질문이다. NP 완전 문제 중 하나가 다항 시간에 풀리면 모든 NP 문제도 다항 시간에 풀리므로 P=NP가 된다.
이 경우 일정 계획, 조합 최적화, 논리 설계 등에서 현재보다 훨씬 강력한 알고리즘을 기대할 수 있다. 반대로 암호 시스템 중 일부는 수학적 문제를 풀기 어렵다는 가정에 의존하므로, P=NP가 증명되면 보안 설계 전반을 다시 검토해야 할 가능성이 있다.
다만 현재 P와 NP가 같은지 다른지는 증명되지 않았다. 이 문제는 1971년 스티븐 쿡과 레오니트 레빈이 독립적으로 정식화했으며, 클레이 수학연구소의 밀레니엄 문제 가운데 하나로 소개되고 있다.
12 | 실제 프로그램은 어떻게 다루는가
NP 완전 문제를 현실에서 만났다고 해서 무조건 계산을 포기하는 것은 아니다. 입력 크기가 작으면 모든 조합을 확인하는 완전 탐색도 충분할 수 있다.
입력이 커지면 다음 방법을 조합한다.
- 정확한 답 대신 충분히 좋은 해를 찾는 근사 알고리즘
- 가능성이 낮은 경우를 일찍 제거하는 가지치기
- 특정 구조의 입력에서만 작동하는 동적 계획법
- 좋은 해를 빠르게 찾는 휴리스틱과 메타휴리스틱
- 문제의 일부 조건을 제한해 다항 시간으로 푸는 특수 알고리즘
따라서 ‘NP 완전’은 실무에서 사용 불가라는 판정이 아니라, 문제 크기와 정확도 요구 수준을 함께 검토해야 한다는 신호에 가깝다.
13 | 흔한 오해와 주의점
NP는 ‘Non-Polynomial’의 약자인가
일반적으로 NP는 ‘비결정적 다항 시간’을 뜻한다. 이름만 보고 모든 NP 문제가 비다항 시간이라고 해석하면 안 된다. P에 속하는 문제도 NP에 포함된다.
NP 완전이면 반드시 지수 시간이 걸리는가
현재 알려진 다항 시간 알고리즘이 없다는 것과 지수 시간이 반드시 필요하다는 것은 다르다. 후자를 증명하려면 P와 NP가 다르다는 사실 자체를 증명해야 하는데, 아직 해결되지 않았다.
모든 최적화 문제는 NP 완전인가
그렇지 않다. 문제의 결정 버전, 입력 표현 방식, 제약 조건에 따라 복잡도 분류가 달라진다. 이름이 비슷한 문제라도 특정 조건에서는 효율적으로 풀릴 수 있다.
14 | 공부할 때 기억할 구조
NP 완전 문제를 정리할 때는 다음 순서로 생각하면 이해가 빠르다.
- 문제가 결정 문제인지 확인한다.
- 후보 해답을 빠르게 검증할 수 있는지 살핀다.
- 다른 NP 문제를 해당 문제로 바꾸는 환원이 가능한지 본다.
- 문제의 입력 크기가 커질 때 가능한 경우의 수가 어떻게 증가하는지 확인한다.
- 정확한 알고리즘, 근사 알고리즘, 휴리스틱 중 어떤 접근이 필요한지 구분한다.
한 문장으로 요약하면, NP 완전 문제는 ‘답을 확인하는 것은 빠르지만 답을 찾는 일반적인 방법은 어려울 수 있고, NP 전체의 난이도를 대표하는 문제’다.
☑ 체크리스트
- 문제가 예·아니오로 답하는 결정 문제인지 확인하기
- 후보 해답을 다항 시간 안에 검증할 수 있는지 확인하기
- NP-hard와 NP-complete를 구분하기
- 입력 크기가 커질 때 가능한 조합 수가 얼마나 증가하는지 살펴보기
- 정확한 해답이 필요한지, 근사 해답도 가능한지 결정하기
- 문제의 특수 조건 때문에 더 빠른 알고리즘이 가능한지 확인하기
📖 자주하는 질문 Q&A
NP 완전 문제는 풀 수 없는 문제인가요?
아니다. 작은 입력은 완전 탐색으로 풀 수 있고, 특정 구조를 가진 입력은 효율적으로 풀릴 수도 있다. 다만 모든 입력에 대해 빠르게 해결하는 일반 알고리즘은 아직 알려지지 않았다.
NP와 NP 완전은 같은 뜻인가요?
같지 않다. NP는 검증 가능한 문제들의 범주이고, NP 완전은 그중에서도 NP의 모든 문제를 환원할 수 있을 정도로 어려운 문제다.
P=NP가 아직 증명되지 않은 이유는 무엇인가요?
현재 알려진 알고리즘과 증명 기법만으로는 NP 완전 문제에 대해 다항 시간 알고리즘이 존재하는지, 또는 존재하지 않는지를 결정하지 못했기 때문이다. 이 질문 자체가 계산 복잡도 이론의 핵심 미해결 문제로 남아 있다.
외판원 문제는 항상 NP 완전인가요?
외판원 문제는 표현 방식에 따라 구분해야 한다. ‘정해진 거리 이하의 순회 경로가 존재하는가’라는 결정 버전은 NP 완전 문제로 다뤄지지만, 최소 비용을 실제로 구하는 최적화 버전은 보통 NP-hard로 설명한다.
📝 마무리
NP 완전 문제는 단순히 계산이 느린 문제가 아니라, 검증과 탐색의 난이도 차이와 문제 사이의 환원 관계를 통해 정의된다. P와 NP의 관계는 아직 풀리지 않았지만, NP 완전성은 알고리즘을 설계할 때 정확한 해답을 언제까지 요구할 수 있는지 판단하게 해주는 중요한 기준이다.