NP 완전 문제

1. P 문제

P (polynomial) 문제 집합은 다항식 시간 복잡도를 가진 알고리즘이다. 다항식보다 큰 시간 복잡도를 가진 알고리즘은 여러가지가 있는데, 그 중 하나가 NPC 문제 집합이다.

 

2. NPC 문제

NPC 문제는 지수 시간의 시간 복잡도를 가진다. NPC 알고리즘의 특징은 어느 하나의 NPC 문제에 대해서 다항식 시간의 알고리즘을 찾아내면, 모든 다른 NPC 문제도 다항식 시간에 해를 구할 수 있다. 이를 추이 관계 (transitive) 라고 한다. 

 

문제의 변환 (polynomial time reduction) 이란 문제 A를 해결하기 위해 문제 B를 해결하는 알고리즘을 사용하는 것이다. 그러기 위해서는 문제 A의 입력을 문제 B의 입력 형태 (format) 으로 변환시켜야 한다. B 알고리즘의 결과를 A의 해로 변환하여 A 문제를 해결할 수 있다. 

 

예를 들어, A문제와 B문제가 다음과 같다고 하자.

A: 부분 집합의 합 (Subset Sum) 문제 -> 정수 집합 S 에 대하여 S의 부분 집합들 중에서 원소의 합이 K 가 되는 부분 집합 찾는 문제

S={20,35,45,70,80} K=105 일 때, 해는 {35,70}

 

B: 동일한 크기의 분할 (Partition) 문제 -> 정수 집합 S 에 대하여 S를 분할하여 원소들의 합이 같은 2개의 부분 집합 찾는 문제

S={20,35,45,70,80} 일 때,  X={20,35,70}, Y={45,80}

 

이제, A문제의 입력을 B 문제의 입력으로 변환하는 방법을 자세히 알아보자. 

 

[Step 1: 입력 변환] t=s-2K 를 계산해서 집합 S에 추가한다. (s: 집합 S의 모든 원소의 합)

s=250

t=250-(2*105)=40

S={20,35,45,70,80,40}

 

[Step 2: B 알고리즘 수행] t가 추가되었으니 s'=s+t = s+(s-2K) = 2s-2K 로 업데이트 된다. 

이걸 반으로 나누면 s-K 이기 때문에, 분할 문제에서 X 와 Y 의 합은 각각 s-K 이다. 

 

[Step 3: 출력 변환] 분할 문제(B문제)의 해인 X와 Y 중에서 t를 가진 집합에서 t를 제거한다. 그것이 부분집합의 합 문제(A 문제) 의 해가 된다. X-{t}

 

X에서 t를 제외한 원소의 합이 K가 되기 때문이다.  (s-K)-t=(s-K)-(s-2K)=K

X={40,35,70} 에서 40 을 제외한 {35,70} 이 A 문제의 해

 

시간복잡도

Step 1과 3은 단순한 입출력 변환이므로 다항식 시간에 수행된다. 따라서 문제 변환의 시간 복잡도는 Step2 의 시간 복잡도에 의해 결정된다. 

 

 

NPC 문제를 해결하려면 다음의 3가지 중에서 1가지는 포기해야 한다. 

1) 다항식 시간에 해 찾기

2) 모든 입력에 대해 해 찾기

3) 최적해 찾기

 

3. NP 문제

P 문제와 NPC 문제 집합을 둘 다 포함하는 NP 문제 집합은 비결정적 다항식 시간을 가진 문제이다. NP 알고리즘은 해를 찾는 알고리즘이 아니라, 해를 다항식 시간에 "검증" 할 수 있는 알고리즘이다. NP 알고리즘은 추측한 해를 확인하여 "맞다" 또는 "아니다" 로 대답해야 하기 때문에 결정 (decision) 문제로 변형해야 한다. 첫 번째 단계에서는 주어진 입력에 대해서 하나의 해를 '추측' 하고, 두 번째 단계에서 그 해를 다항식 시간에 확인한 후에, 그 해가 "맞다/아니다" 라고 답한다. 예를 들어, "최단 경로의 거리" 를 찾는 문제를 "k보다 짧은 경로가 있는가?" 라는 결정 문제로 변형한다. 

 

4. NP-Hard 문제

 

NP-Hard 문제는, 일반적으로 NP 문제보다 해결하기 더 어렵거나 최소한 그만큼 어려운 문제를 의미한다.

어떤 문제 A에 대해, 모든 NP 문제를 문제 A로 다항식 시간 안에 변환할 수 있다면, 문제 A는 NP-Hard이다. 

즉, 만약 문제 A를 효율적으로 풀 수 있는 알고리즘이 존재한다면, 그것을 이용해 다른 모든 NP 문제도 효율적으로 해결할 수 있다.

 

다만, NP-하드 문제라고 해서 반드시 NP 문제인 것은 아니다. NP-하드 문제는 정답이 맞는지 다항식 시간 내에 검증이 가능하지 않을 수도 있다. 

 

이때, NPC 문제는 NP-하드 문제이면서 동시에 NP 문제이다. 

 

5. NPC 문제 예시

a) SAT (Satisfiability)

부울 변수들이 V 로 표현된 논리식이 여러 개 주어질 때, 이 논리식들을 모두 만족시키는 각 부울 변수 값을 찾는 문제

 

b) 부분집합의 합 (Subset Sum)

주어진 정수의 집합 S의 원소의 합이 K가 되는 S의 부분 집합 찾는 문제

S={2,3,4,8,9} K=20 일 때, 해는 {3,8,9}

 

c) 분할 (Partition)

주어진 정수의 집합 S를 분할하여 원소의 합이 같은 2개의 부분 집합 찾는 문제

S={2,3,4,8,9} 때, X={2,3,8} Y={4,9} 

 

d) 0-1 배낭 (Knapsack)

배낭의 용량이 C 이고, n개의 물건의 각각의 무게와 가치가 w와 v 일때 배낭에 담을 수 있는 물건의 최대 가치 찾는 문제

C = 20kg, 

w1 = 12kg & 20원 , w2 = 8kg & 10원 , w3 = 6kg & 15원 , w4 = 5kg /& 25원

 

물건 2+3+4 = 19kg & 50원

 

e) 정점 커버 (Vertex Cover)

그래프에서 각 간선의 양 끝점들 중에서 적어도 1개의 점을 포함하는 최소 크기의 집합 찾는 문제

f) 독립 집합 (Independence Set)

그래프에서 서로 연결하는 간선이 없는 점들의 최대 크기 집합 찾는 문제

Tip: 정점 커버 해 의 반대

정점커버의 반대

g) 클리크 (Clique)

그래프에서 모든 점들 사이를 연결하는 간선이 있는 최대 크기의 그래프를 찾는 문제

 

h) 그래프 색칠하기 (Graph Coloring)

인접한 점들을 서로 다른 색으로 색칠하는 문제

Tip: 클리크에 속하는 vertex 들은 서로 다른 색깔로 칠한다.

i) 집합 커버 (Set Cover)

주어진 집합 S에 대해서 S의 부분 집합들이 주어질 때, 이 부분집합들 중에서 합집합하여 S 와 같게 되는 최소의 부분 집합 찾는 문제

j) 최장 경로 (Longest Path)

시작점에서 도착점까지의 가장 긴 경로를 찾는 문제. 단, 찾는 경로에는 반복되는 점이 없어야 한다.

k) 여행자 (Traveling Salesman)

임의의 한 점에서 출발하여, 다른 모든 점들을 1번씩만 방문하고, 다시 시작점으로 돌아오는 경로 중에서 최단 경로 찾는 문제

Tip: 모든 엣지의 크기가 1

모든 엣지의 크기가 1

l) 해밀토니안 사이클 (Hamiltonian Cycle)

간선의 가중치가 동일한 여행자 문제

m) 통채우기 (Bin Packing)

n개의 물건이 주어지고 용량이 C 일떄, 가장 적은 수의 통을 사용하여 모든 물건을 통에 채우는 문제

Tip: 내림차순 정렬 후 큰 것 부터 집어넣기

n) 작업 스케줄링 (Job Scheduling)

모든 작업이 가장 빨리 종료되도록 작업을 기계에 배정하는 문제

Tip: 최대한 균등하게

6. NPC 변환

0-1 배낭  -> 부분 집합의 합

정점 커버 -> 독립 집합 or 집합 커버

독립 집합 -> 클리크

그래프 색칠하기 -> 클리크