알고리즘의 성능을 평가할 때 우리는 Big-O 표기법을 사용한다. 어떤 문제를 해결하는 방법, 즉 알고리즘은 여러 가지가 있을 수 있으며, 이 알고리즘의 성능을 비교하고 평가할 때 Big-O 표기법이 쓰인다.
반면 P-NP 문제는 조금 다른 관점에서 문제를 바라본다. 어떤 문제가 주어졌을 때 그 문제가 “쉬운 문제”인지 “어려운 문제”인지, 더 나아가 현실적으로 해결 가능한 문제인지 아닌지를 판단하는 척도가 된다
결정 문제와 최적화 문제
P와 NP의 개념을 이해하기 전에, 먼저 결정 문제(Decision Problem)가 무엇인지 알아야 한다.
결정 문제(Decision Problem)
결정 문제란 어떤 문제가 주어졌을 때 “Yse” 또는 “No”로 대답할 수 있는 문제를 말한다
- “10은 2로 나눴을 때 정확히 나누어 쩔어지는가?” → Yes
- “7은 짝수인가?” → No
최적화 문제(Optimization Problem)
최적화 문제는 어떤 상황이 주어지고 거기서 최적의 해를 찾으라는 문제이다
- “지도가 주어졌을 때, A 지점에서 E 지점까지 가는 경로 중 가장 짧은 경로를 구하시오”
이 문제는 Yes나 No로 대답할 수없고, A 지점에서 E 지점까지 갈 수 있는 모든 경로를 탐색하여 그 중 최적의 해를 구해야 한다
최적화 문제 → 결정 문제로 변환
대부분의 최적화 문제는 결정 문제로 바꿀 수 있다
- 최적화 문제: “A 지점에서 E 지점까지 가는 가장 짧은 경로를 구하시오”
- 결정 문제: “A 지점에서 E 지점까지 가는 경로 중 비용이 10보다 작은 경로가 존재하는가?
두 번째 질문에는 Yes와 No로 대답할 수 있으므로, 이 문제를 결정 문제가 되었다
P 문제 (Polynomial Time Problems)
P 문제는 결정 문제가 주어졌을 때 결정론적 튜링 머신(Deterministic Turing Machine)을 사용해 다항 시간(Polynomial Time)내에 답을 구할 수 있는 문제이다.
결정론적 튜링 머신
결정론적 튜링 머신은 현재 상태에서 다음 상태로 이동할 때 다음 상태가 유일하게 결정되는 머신이다. 간단하게 생각하면 오늘날의 컴퓨터로 이해하면 된다
프로그래밍에서 if-else로 분기가 나뉘는 것을 보고 “여러 상태로 나뉘는 것 아닌가”라고 착각하기 쉽지만, if문이 참이면 if문이 수행되는 유일한 상태로, 거짓이졈 else문이 수행되는 유일한 상태로 결정된다
public class DeterministicExample {
public static void main(String[] args) {
int num = 10;
// 결정론적 튜링 머신의 동작 방식
// num의 값에 따라 다음 상태가 '유일하게' 결정됨
if (num == 10) {
// num이 10이면 이 블록만 실행 (유일한 다음 상태)
System.out.println("num은 10입니다.");
} else {
// num이 10이 아니면 이 블록만 실행 (유일한 다음 상태)
System.out.println("num은 10이 아닙니다.");
}
}
}
┌─────────────────────────────────────────────────────────────────┐ │ 결정론적 튜링 머신 (Deterministic Turing Machine) │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ ● (시작) │ │ │ │ │ ▼ │ │ ● (상태 1) │ │ │ │ │ ▼ │ │ ● (상태 2) │ │ │ │ │ ▼ │ │ ● (종료: accept or reject) │ │ │ │ 특징: 현재 상태에서 다음 상태가 항상 '하나'로 결정됨 │ │ │ └─────────────────────────────────────────────────────────────────┘
다항 시간(Polynomial Time)
다항 시간이란 문제를 해결하는 데 걸리는 시간이 다항식으로 표현할 수 있는 것을 말한다. 다항식은 n² – 2n + 3과 같이 입력 n에 대하 여러 항이 존재하는 식을 말한다. 이 다항식을 Big-O 표기법으로 표현하면 O(n²)이다
다항 시간에 대항하는 시간 복잡도
| 시간 복잡도 | 이름 | 다항 시간 |
| O(1) | 상수 시간 | O |
| O(log n) | 로그 시간 | O |
| O(n) | 선형 시간 | O |
| O(n log n) | 선형 로그 시간 | O |
| O(n²) | 이차 시간 | O |
| O(n³) | 삼차 시간 | O |
| O(2ⁿ) | 지수 시간 | X |
| O(n!) | 팩토리얼 시간 | X |
상수 시간과 로그 시간은 다항 시간보다 더 작으므로, “다항 시간 내에 잡을 구할 수 있다”고 말할 때는 상수 시간, 로그 시간, 다항 시간 모두를 포함한다
반면 지수 시간(O(2ⁿ))은 다항 시간보다 크기 때문에 다항 시간 내에 해결할 수 없다
P 문제의 예시: 정렬문제
P 문제의 대표적인 예시로 정렬 문제가 있다. 정렬 문제를 해결하는 가장 기본적인 알고리즘인 버블 정렬(Bubble Sort)을 통해 살펴보자
문제: 배열 [3, 4, 1, 2]를 오름차순 [1, 2, 3, 4]로 정렬하시오
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 외부 루프: n-1번 반복
for (int i = 0; i < n - 1; i++) {
// 내부 루프: 인접한 두 원소 비교
for (int j = 0; j < n - 1 - i; j++) {
// 결정 문제: "arr[j]가 arr[j+1]보다 큰가?"
if (arr[j] > arr[j + 1]) {
// Yes: 두 원소의 위치를 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
// No: 아무 일도 하지 않음
}
}
}
public static void main(String[] args) {
int[] arr = {3, 4, 1, 2};
System.out.println("정렬 전: ");
printArray(arr);
bubbleSort(arr);
System.out.println("정렬 후: ");
printArray(arr);
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
버블 정렬의 동작 과정
┌─────────────────────────────────────────────────────────────────┐ │ 버블 정렬 동작 과정 │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ 초기 상태: [3, 4, 1, 2] │ │ │ │ ═══════════════════════════════════════════════════════════ │ │ 1라운드: 가장 큰 수(4)를 맨 뒤로 이동 │ │ ═══════════════════════════════════════════════════════════ │ │ │ │ Step 1: [3, 4, 1, 2] │ │ ↑ ↑ │ │ "3 > 4?" → No (교환 안 함) │ │ │ │ Step 2: [3, 4, 1, 2] │ │ ↑ ↑ │ │ "4 > 1?" → Yes (교환!) │ │ 결과: [3, 1, 4, 2] │ │ │ │ Step 3: [3, 1, 4, 2] │ │ ↑ ↑ │ │ "4 > 2?" → Yes (교환!) │ │ 결과: [3, 1, 2, 4] ← 4가 제자리를 찾음! │ │ │ │ ═══════════════════════════════════════════════════════════ │ │ 2라운드: 두 번째로 큰 수(3)를 제자리로 이동 │ │ ═══════════════════════════════════════════════════════════ │ │ │ │ Step 1: [3, 1, 2, 4] │ │ ↑ ↑ │ │ "3 > 1?" → Yes (교환!) │ │ 결과: [1, 3, 2, 4] │ │ │ │ Step 2: [1, 3, 2, 4] │ │ ↑ ↑ │ │ "3 > 2?" → Yes (교환!) │ │ 결과: [1, 2, 3, 4] ← 3이 제자리를 찾음! │ │ │ │ ═══════════════════════════════════════════════════════════ │ │ 3라운드: 세 번째로 큰 수(2) 확인 │ │ ═══════════════════════════════════════════════════════════ │ │ │ │ Step 1: [1, 2, 3, 4] │ │ ↑ ↑ │ │ "1 > 2?" → No (교환 안 함) │ │ 결과: [1, 2, 3, 4] ← 정렬 완료! │ │ │ └─────────────────────────────────────────────────────────────────┘
버블 정렬의 시간 복잡도 분석
배일의 길이가 n 일 때
- 1 라운드: (n-1)번 비교
- 2 라운드: (n-2)번 비교
- …
- (n-1) 라운드: 1번 비교
총 비교 횟수 = (n – 1) + (n – 2) + … + 1 = n(n-1)/2 = O(n²)
n²은 다항식이므로 버블 정렬은 다항 시간 내에 완료된다. 따라서 정렬 문제는 P 문제로 분류된다
NP 문제(Nondeterministic Polynomial Time Problems)
NP 문제는 결정 문제가 주어졌을 때 비결정론적 튜링 머신(Nondeterministic Turing Machine)을 사용해 다항 시간 내에 답을 구할 수 있는 문제이다
비결정론적 튜링 머신
비결정론적 튜링 머신은 현재 상태에서 다음 상태로 이동할 때 다음 상태의 개수가 유일하지 않은 머신이다. 이는 현실 세계에서는 존재하지 않는 상상 속의 기계이다
┌─────────────────────────────────────────────────────────────────┐ │ 비결정론적 튜링 머신 (Nondeterministic Turing Machine) │ ├─────────────────────────────────────────────────────────────────┤ │ ● (시작) │ │ ╱ ╲ │ │ ╱ ╲ │ │ ▼ ▼ │ │ ● ● │ │ ╱ ╲ ╱ ╲ │ │ ▼ ▼ ▼ ▼ │ │ ● ● ● ● │ │ │ │ │ │ │ │ ▼ ▼ ▼ ▼ │ │ accept reject accept reject │ │ or or or or │ │ reject accept reject accept │ │ │ │ 특징: 현재 상태에서 다음 상태가 '여러 개'로 분기됨 │ │ 모든 경로를 '동시에' 탐색할 수 있음 (상상의 기계) │ │ │ └─────────────────────────────────────────────────────────────────┘
도둑과 금고 비유로 이해하기
결정론적 튜링 머신의 경우
도둑이 있고, 3단계로 갈라지는 길이 있다고 가정한다. 각 단계마다 길이 2개로 갈라지면 총 8개의 경로가 생긴다
결정 문제: “금고가 존재하는가?”
결정론적 튜링 머신 (일반 컴퓨터)은 한 번에 하나의 경로만 탐색할 수 있다
┌───────────────────────────────────────────────────────┐ │ 결정론적 튜링 머신의 탐색 방식 │ ├───────────────────────────────────────────────────────┤ │ │ │ ● (시작) │ │ ╱ ╲ │ │ ╱ ╲ │ │ ● ● │ │ ╱ ╲ ╱ ╲ │ │ ● ● ● ● │ │ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ │ │ ● ● ● ● ● ● ● ● │ │ ↑ 💰 │ │ (도둑이 한 경로씩 탐색) (금고) │ │ │ │ 도둑은 한 번에 하나의 길만 탐색 가능 │ │ 최악의 경우: 8개의 경로를 모두 탐색해야 함 → O(2ⁿ) │ │ │ └───────────────────────────────────────────────────────┘
만약 20단계로 갈라진다면? → 2²⁰ = 1,048,576개의 경로
이처럼 문제를 해결하는 데 O(2ⁿ)과 같이 지수에 n이 있으면 이를 지수시간이라고 한다. 지수 시간은 입력이 조금만 커져도 해결 시간이 매우 오래 걸리기 때문에 결정론적 튜링 머신으로는 현실적으로 해결하기 어렵다
비결정론적 튜링 머신의 경우
비결정론적 튜링 머신은 무한한 컴퓨팅 능력을 가정한 상상의 기계이다. 마치 도둑이 분신술을 써서 모든 경로를 동시에 탐색하는 것과 같다
┌─────────────────────────────────────────────────────────────────┐ │ 비결정론적 튜링 머신의 탐색 방식 │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ 🥷 (도둑) │ │ ╱ ╲ │ │ 분신술! ╱ ╲ 분신술! │ │ 🥷 🥷 │ │ ╱ ╲ ╱ ╲ │ │ 🥷 🥷 🥷 🥷 │ │ ╱ ╲ ╱ ╲ ╱ ╲ ╱ ╲ │ │ 🥷 🥷🥷 🥷 🥷 🥷 🥷 🥷 │ │ ↓ │ │ 💰 │ │ "YES! 금고 발견!" │ │ │ │ 모든 분신이 동시에 모든 경로를 탐색 │ │ 하나의 분신이 금고를 발견하면 → 즉시 "YES!" 응답 │ │ 탐색 시간: O(n) (단계 수만큼만 소요) │ │ │ └─────────────────────────────────────────────────────────────────┘
비결정론적 튜링 머신은 매 선택지에서 모든 선택을 동시에 할 수 있으므로, 하나의 분신이라도 금고를 발견하면 즉시 “YES”를 외칠 수 있다.
NP 문제의 핵심 특성
NP 문제는 결정론적 튜링 머신(일반 컴퓨터)의 관점에서 설명하면
- 다항 시간 내에 답을 직접 구하기는 어렵다 (지수 시간이 걸릴 수 있음)
- 하지만 “힌트(후보 해답)”가 주어지면 그것이 정답인지 다항 시간 내에 검증할 수 있다
예를 들어, 도둑 문제에서
- “금고가 존재하는가?”라는 문제를 직접 푸는 것은 어렵지만(모든 경로 탐색 필요)
- “이 경로에 금고가 있다”라는 힌트가 주어지면, 그 경로만 따라가서 다항 시간 내에 검증 가능
P와 NP의 관계
중요: 모든 P 문제는 NP 문제이기도 하다
왜냐하면 결정론적 튜링 머신으로 다항 시간 내에 풀 수 있는 문제(P문제)는 당연히 비결정론적 튜링 머신으로도 다항 시간 내에 풀 수 있기 때문이다
┌─────────────────────────────────────────────────────────────────┐ │ P ⊆ NP 관계 │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ ┌───────────────────────────┐ │ │ │ NP │ │ │ │ │ │ │ │ ┌───────────────┐ │ │ │ │ │ P │ │ │ │ │ │ │ │ │ │ │ │ (정렬, 검색 │ │ │ │ │ │ 최단경로) │ │ │ │ │ └───────────────┘ │ │ │ │ │ │ │ │ (P가 아닌 NP 문제들?) │ │ │ │ │ │ │ └───────────────────────────┘ │ │ │ │ 모든 P 문제는 NP 문제에 포함됨 │ │ P = NP 인지는 아직 밝혀지지 않음! │ │ │ └─────────────────────────────────────────────────────────────────┘
NP-Hard 문제
어떤 NP 문제들이 있을 때, 모든 NP 문제들을 다항 시간 내에 어떤 문제 A로 환원(reduction) 시킬 수 있다면, 그 문제 A를 NP-Hard라고 부른다
환원(reduction)
환원이란 하나의 문제를 다른 문제로 변환하여 해결하는 것을 말한다. 만약 문제 A가 해결되면 문제 B도 쉽게 해결될 수 있자면, “문제 B는 문제 A로 환원될 수 있다”고 한다
예시로 이해하기
다음과 같은 문제들이 있다고 가정한다 (실제로는 NP문제가 아니지만, 설명을 위한 예시이다)
| 문제 | 설명 |
| 문제 A | n개의 숫자를 오름차순으로 정렬하라 |
| 문제 B | n개의 숫자 중 가장 작은 값을 구하라 |
| 문제 C | n개의 숫자 중 가장 큰 값을 구하라 |
| 문제 D | n개의 숫자 중 중간 값을 구하라 |
만약 문제 A(정렬)가 해결되면
- 문제 B: 정렬된 배열의 첫 번째 원소 = 최솟값
- 문제 C: 정렬된 배열의 마지막 원소 = 최댓값
- 문제 D: 정렬된 배열의 가운데 원소 = 중간값
┌─────────────────────────────────────────────────────────┐ │ 환원(Reduction) 개념 │ ├─────────────────────────────────────────────────────────┤ │ │ │ 문제 B (최솟값) ──┐ │ │ │ │ │ 문제 C (최댓값) ──┼──→ 문제 A (정렬) │ │ │ │ │ 문제 D (중간값) ──┘ │ │ │ │ │ │ 문제 A가 해결되면 → 문제 B, C, D 모두 쉽게 해결됨 │ │ │ │ "문제 B, C, D는 문제 A로 환원될 수 있다" │ │ "문제 A는 가장 어려운 문제" (이 맥락에서) │ │ │ └─────────────────────────────────────────────────────────┘
NP-Hard의 특징
- NP-Hard 문제가 반드시 NP 문제일 필요는 없다
- NP-Hard 문제는 해결 가능 여부조차 불분명한 경우가 있다
- “가장 어려운 문제” 그룹에 속한다
NP-Complete 문제
NP-Complete 문제는 NP-Hard이면서 동시에 NP에도 속하는 문제이다
NP-Complete = NP-Hard ∩ NP
NP-Complete 문제는 NP-Hard이면서 동시에 NP에 속하는 문제이다.
| 구분 | NP-Complete | NP-Hard |
| NP에 속하는가? | 예 | 아닐 수 있음 |
| 해결 가능 여부 | 해결 가능 (검증 가능) | 불분명할 수 있음 |
| 난이도 | NP 중 가장 어려운 문제 | NP보다 어려울 수 있음 |
┌──────────────────────────────────────────────────────┐ │ NP-Complete 문제의 위치 │ ├──────────────────────────────────────────────────────┤ │ │ │ ┌─────────────────────┐ │ │ │ NP-Hard │ │ │ │ │ │ │ │ ┌─────────────┐ │ │ │ │ │ NP-Complete │ │ │ │ │ │ │ │ │ │ │ └──────┬──────┘ │ │ │ │ │ │ │ │ └──────────│──────────┘ │ │ │ │ │ ┌───────────────┴───────────────┐ │ │ │ NP │ │ │ │ │ │ │ │ ┌───────────┐ │ │ │ │ │ P │ │ │ │ │ └───────────┘ │ │ │ └───────────────────────────────┘ │ │ │ │ NP-Complete: NP-Hard와 NP의 교집합 │ │ (NP 문제 중 가장 어려운 문제들) │ │ │ └──────────────────────────────────────────────────────┘
외판원 문제(Traveling Salesman Problem, TSP)
외판원 문제는 P-NP 문제를 이해하는 데 가장 유명한 예시 중 하나이다
문제 설명
여러 도시들이 있고, 도시들은 도로로 연결되어 있다. 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때 모든 도시들은 단 한 번 만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하라
┌─────────────────────────────────────────────────────────────────┐ │ 외판원 문제 (TSP) 예시 │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ 도시 A │ │ ╱ │ ╲ │ │ 25╱ │10 ╲15 │ │ ╱ │ ╲ │ │ ╱ │ ╲ │ │ 도시 B ────│───── 도시 D │ │ ╲ 10│ ╱ │ │ 10╲ │ ╱5 │ │ ╲ │ ╱ │ │ ╲ │ ╱ │ │ 도시 C │ │ │ │ 도시 B ─────────── 45 ─────────── 도시 D │ │ │ │ 숫자는 도시 간 이동 비용 (거리) │ │ │ │ 목표: A에서 출발해 모든 도시를 한 번씩 방문하고 │ │ 다시 A로 돌아오는 최소 비용 경로 찾기 │ │ │ └─────────────────────────────────────────────────────────────────┘
외판원 최적 버전 (TSP-Optimal Version) – NP-Hard
문제: “모든 도시를 방문하고 돌아오는 최소 비용 경로로 구하라”
이 버전은 NP-Hard이다
- 해밀턴 경로 문제(모든 정점을 한 번씩 지나는 경로 찾기)가 이 문제로 환원될 수 있다
- 비결정론적 튜링 머신으로도 다항 시간 내에 최소 비용 경로를 찾을 수 있다
- 따라서 NP 문제가 아님 -> NP-Complete가 될 수 없다
외판원 결정 버전(TSP-Decision Version) – NP-Complete
문제: “모든 도시를 방문하고 돌아오는 비용이 n 이하인 경로가 존재하는가?”
이 버전은 NP-Complete이다
- Yes/No로 대답할 수 있는 결정 문제
- 해밀턴 경로 문제가 이 문제로 환원될 수 있음 → NP-Hard
- “이 경로가 조건을 만족하는가?”를 다항 시간 내에 검증할 수 있음 → NP
- NP-Hard ∩ NP = NP-Complete
밀레니엄 문제와 P VS NP
클레이 수학 연구소가 선정한 7개의 미해결 수학 문제로, 각 문제를 해결하면 100만 달러 상금이 수여된다 (츄베릅)
| 문제 | 분야 | 상태 |
| P vs NP 문제 | 컴퓨터 과학 | 미해결 |
| 호지 추측 | 대수 기하학 | 미해결 |
| 리만 가설 | 수론 | 미해결 |
| 양-밀스 질량 간극 가설 | 수리 물리학 | 미해결 |
| 나비에-스토크스 방적식 | 유체역학 | 미해결 |
| 버치-스위너턴다이어 추측 | 대수 기하학/수론 | 미해결 |
| 푸앵카레 추측 | 위상 수학 | 해결(2003) |
P VS NP 문제
핵심 질문: “P 집합과 NP 집합이 같은가?”. 즉, “검증하기 쉬운 문제는 풀기도 쉬운가?”
┌─────────────────────────────────────────────────────────────────┐ │ P vs NP 문제 │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ 경우 1: P ≠ NP │ │ ════════════════════════════════════ │ │ │ │ ┌─────────────────────┐ │ │ │ NP-Hard │ │ │ │ ┌──────────────┐ │ │ │ │ │ NP-Complete │ │ │ │ │ └──────┬───────┘ │ │ │ └─────────│───────────┘ │ │ ┌─────────┴───────────┐ │ │ │ NP │ │ │ │ ┌──────────┐ │ │ │ │ │ P │ │ │ │ │ └──────────┘ │ │ │ └─────────────────────┘ │ │ │ │ 의미: NP-Complete 문제를 다항 시간에 푸는 알고리즘은 없다 │ │ │ │ ───────────────────────────────────────────────────────── │ │ │ │ 경우 2: P = NP │ │ ════════════════ │ │ │ │ ┌─────────────────────┐ │ │ │ NP-Hard │ │ │ │ ┌──────────────────┴───┐ │ │ │ │ P = NP │ │ │ │ │ = NP-Complete │ │ │ │ │ │ │ │ │ └──────────────────────┘ │ │ └─────────────────────────┘ │ │ │ │ 의미: 모든 NP 문제를 다항 시간에 풀 수 있다! │ │ → 암호학 붕괴, 최적화 문제 혁신 등 │ │ │ └─────────────────────────────────────────────────────────────────┘
P = NP라면가 증명된다면
- 모든 NP 문제(외판원 문제, 해밀턴 경로 등)를 다항 시간에 해결하는 알고리즘이 존재함
- 현재 암호화 시스템(RSA 등) 대부분이 무력화됨
- 물류, 스케줄링, 단백질 접힘 등 수많은 최적화 문제가 효율적으로 해결 가능
P ≠ NP라면가 증명된다면
- NP-Complete 문제를 다항 시간에 푸는 알고리즘을 찾으려는 시도가 무의미함
- 근사 알고리즘, 휴리스틱에 더 집중해야 함
- 암호화 시스템의 안전성이 수학적으로 보장됨