[알고리즘] NP - 완비
1. 문제의 종류
- 세상에 다양한 종류의 문제가 존재하고, 이 문제들은 해결 가능성에 따라 풀 수 있는 문제와 풀 수 없는 문제로 나눌 수 있음.
- 컴퓨터 과학의 정지 문제나 힐버트의 열 번째 문제는 우리의 논리 체계하에서 풀 수 없는 대표적인 문제.
- 풀 수 있는 문제는 해결하는 데 필요한 시간에 따라 현실적인 시간에 풀 수 있는 문제와 그렇지 않은 문제로 나뉨.
- 현실적인 시간에 풀 수 없는 문제는 주어진 시간 범위에서 근사해를 구하는 것을 목표로 할 수 밖에 없음.
- NP-완비는 현실적인 시간에 풀 수 없다 추정되면서 서로 강력한 논리적 연관성을 가진 특이한 문제군에 관한 것.
- 보통 다항식 시간은 현실적인 시간이라 간주하고, 지수 시간은 비현실적인 시간이라 간주함.
2. Yes / No 문제와 최적화 문제
- 문제는 답의 종류에 따라 분류가능 ( Yes/No 문제, 해를 찾는 문제 )
- NP-완비 이론은 이론의 전개를 쉽게 하기 위해서 Yes / No 문제만 대상으로 함.
- 최적화 문제도 모두 그에 대응되는 Yes/No 문제로 바꾼 다음 다룸.
- Yes / No 문제가 어려움을 보이면 최적화 문제도 어려움을 알 수 있게 해줌.
- Yes/No 문제를 다른 말로는 결정 문제라고 함.
3. NP ( Nondeterministic Polynomial )
- NP-완비군은 NP 군에 속하는 문제 중 특수한 관계를 가진 문제들의 집합.
- P군 : 다항식 시간에 해결할 수 있는 문제들의 군. 다항식 시간에 Yes 또는 No 대답을 할 수 있으면 P.
- NP군 : 비결정론적 다항식 시간에 해결할 수 있는 문제군. Yes라는 근거가 주어졌을 때 그것이 옳은 근거임을 다항식 시간에 확인해줄 수 있는 문제.
- NP-완비 이론에서는 NP-완비의 필요조건인 NP-하드라는 성질에 가장 주의를 기울여야 함.
P와 NP의 포함 관계
- 모든 P군의 문제는 당연히 NP군에도 속함. ( P ⊆ NP )
- 그렇지만 NP에 P가 아닌 문제가 포함되어 있는지는 아직 아무도 모름.
- P와 NP는 크기 차이가 큰 집합일 것 같지만 아직 증명되지 않음.
4. 다항식 시간 변환
- 결정 문제 A가 다항식 시간에 해결 가능한지 알고 싶음. 다항식 시간에 해결 가능한 결정 문제 B를 이미 알고있음.
- 문제 A를 다항식 시간에 문제 B로 변형할 수 있고 이 변형의 결과 문제 B의 대답과 문제 A의 대답이 항상 일치하면, 문제 A도 다항식 시간에 해결 가능함.
- 문제 A를 푸는 데 걸리는 시간은 문제 B로 변환하는 시간과 문제 B를 푸는 시간을 합한 것.
- 즉 문제 A는 다항식 시간에 문제 B로 바꾸어 풀 수 있음.
- NP-완비군에 속하는 문제들은 모두 서로 이런 논리적 연결 관계를 가지고 있음.
다항식 시간 변환
- 문제 A의 사례 α, 문제 B의 사례 β로 바꾸되 다음 성질을 만족하면 다항식 시간 변환이라 하고, 이를 α ≤ ₚ β로 표기함.
① 변환은 다항식 시간에 이루어짐.
② 두 사례의 답은 일치함.
- 다항식 시간 변환은 ≤ ₚ로 표기함. 이 정의처럼 사례 α를 사례 β로 다항식 시간 변환할 수 있으면 α ≤ ₚ β로 표기함.
해밀토니안 사이클
- 그래프의 모든 정점을 한 번씩만 방문하고 출발점으로 돌아오는 경로를 뜻함.
- 해밀토니안 사이클 문제는 주어진 무향 그래프에서 해밀토니안 사이클이 존재하는지 묻는 문제.
HAM-CYCLE ( 해밀토니안 사이클 문제 )
- 입력 : 무향 그래프 G=(V,E)
- 질문 : G에 해밀토니안 사이클이 존재하는가?
TSP ( 순회 세일즈맨 문제 )
- 가중치 있는 완전 그래프에서 길이가 가장 짧은 해밀토니안 사이클의 길이를 찾는 문제.
- 완전 그래프는 모든 정점 사이에 간선이 있는 그래프이므로 해밀토니안 사이클은 무조건 존재함.
- 정확히 말하면 총 (n-1)!가지의 해밀토니안 사이클이 존재함.
- TSP는 이 중 가장 짧은 것을 찾는 문제.
TSP ( 순회 세일즈맨 문제 )
- 입력 : 양의 가중치를 갖는 무향 완전 그래프 G=(V,E), 양의 실수K
- 질문 : G에 길이가 K 이하인 해밀토니안 사이클이 존재하는가?
5 NP-완비
- NP-완비군은 지금까지 기술로는 다항식 시간에 풀기 어렵다고 판단되면서 서로 밀접한 논리적 연결 관계를 가진 문제의 집합.
- NP-완비군에 속하는 문제 중 다항식 시간에 해결 가능함을 보인 것은 없음.
- 한 문제가 다항식 시간에 해결 가능하면 이 문제의 답으로 다른 문제의 답도 말해줄 수 있어 이 군에 속한 모든 문제가 다항식 시간에 풀림.
NP-하드
- 문제 A가 다음 조건을 만족하면 NP-하드.
모든 NP 문제 L에 대하여 L ≤ ₚ A.
NP-완비
- 문제 A가 다음 두 가지 조건을 만족하면 NP-완비.
① A는 NP다.
② A는 NP-하드다.
- ≤ ₚ는 다항식 시간 변환을 뜻함.
- 어떤 문제 A가 NP-완비라면 이것은 NP에 속하고, 다른 모든 NP 문제가 A로 다항식 시간 변환 가능함을 뜻함.
- NP-하드는 NP-완비보다 넓은 범위의 문제를 포함함.
- 따라서 NP-완비인 문제를 NP-하드라고 해도 괜찮음.
- 어떤 문제가 NP-하드임을 보이는 것은 매우 어려움. 모든 NP 문제, 알려지지 않은 수많은 NP 문제까지 모두 포함함.
- NP 문제의 특성을 기반으로 포괄적으로 증명해야 함.
- 이런 난관을 극복하기 위해 NP-하드의 증명은 이것을 사용함. 이 조건을 만족하면 역시 NP-하드가 됨.
- 다음 조건을 만족하면 문제 A는 NP-하드다.
어떤 알려진 NP-하드 문제 C에 대하여 C ≤ ₚ A이다.
6. NP-완비 문제들
- NP-완비성 증명의 핵심은 서로 다른 두 문제 간의 다항식 시간 변환.
- 전혀 관계가 없어 보이는 문제들 간에도 변환이 됨을 볼 수 있을 것임.
문제 A가 NP-완비임을 보이기 위한 작업
① A가 NP임을 보임.
② 알려진 NP-하드 문제 C를 택하여 다항식 시간에 C의 사례를 A의 사례로 바꾸는 알고리즘을 기술함.
③ 위 ②의 결과 사례 C와 사례 A의 Yes/No 대답이 일치함을 보임.
- ②와 ③은 ②의 NP-하드 여부, 즉 다항식 시간 변환 가능성을 보이는 과정.
NP-완비 문제 예 : 두 정점 간의 최장 거리 구하기
- HAM-PATH-2-POINTS 정의
HAM-PATH-2-POINTS ( 두 점 사이의 해밀토니안 경로 문제 )
- 입력 : 그래프 G=(V, E), V의 두 정점 s, t
- 질문 : 정점 s에서 정점 t에 이르는 해밀토니안 경로가 존재하는가?
- 그래프 G=(V, E)의 해밀토니안 경로는 V의 모든 정점을 한 번씩 거치는 단순 경로를 뜻함.
- 이 그림은 임의의 그래프와 이 그래프에 있는 해밀토니안 경로 중 3개를 보여주는 예.
- HAM-PATH-2-POINTS 문제는 주어진 두 정점을 양 끝점으로 하는 해밀토니안 경로가 있는지 묻는 문제.
- 이 문제는 NP-완비 문제.
LONGEST-PATH ( 최장 경로 문제 )
- 입력 : 간선이 양의 가중치를 가지는 그래프 G=(V,E), V의 두 정점 s, t, 양의 상수 K
- 질문 : 정점 s에서 정점 t에 이르는 길이 K 이상인 단순 경로가 존재하는가?
LONGEST-PATH는 NP-완비다.
>> 증명 :
① 먼저 LONGEST-PATH는 NP임을 증명한다.
정점 s에서 정점 t에 이르는 길이 K 이상인 단순 경로가 주어질 때 이것이 길이 K 이상임을 보이는 것은 단순히 경로만 따라가면서 간선들이 모두 E에 속하고 가중치를 합해 K이상인지 확인하면 됨. 이것이 길이 K 이상임을 보이는 것은 단순히 경로만 따라가면서 간선들이 모두 E에 속하고 가중치를 합해 k이상인지 확인하면 됨. 다항식 시간에 확인할 수 있어 LONGEST-PATH는 NP임.
7. NP- 하드를 최적화 문제로 확장하기
다항식 시간 변환의 확장 버전
- 문제 A의 사례 α, 문제 B의 사례 β로 바꾸되 다음 성질을 만족하면 다항식 시간 변환이라 하고, 이를 α ≤ ₚ β로 표기함.
① 변환은 다항식 시간에 이루어짐.
② β의 답을 이용해서 α의 답을 구할 수 있음.
- ② β에서 α로 한 방향만 이야기하고 있지만, 이를 결정 문제에 적용하면 결국 양방향으로 성립하게 되기 때문.
- 확장 버전이 다항식 시간 변환의 원래 의도에 더 충실한 버전.
- 이제 이 정의를 이용하면 최적화 문제도 NP-하드 범주에 포함시킬 수 있습니다.
최적화 TSP ( 순회 세일즈맨 문제의 최적화 버전 )
- 입력 : 양의 가중치를 갖는 무향 완전 그래프 G = ( V, E)
- 질문 : G에서 길이가 가장 짧은 해밀토니안 사이클의 길이는 얼마인가?