11장. NP-완비NP-Completeness 쉽게 배우는 알고리즘 11장. NP-완비NP-Completeness

NP-완비NP-Completeness 그것이 지닌 잠재적 영향력은 제대로 인식하지 못했다. -스티븐 쿡 때로는 어떤 것이 불가능하다는 사실이 유용할 때도 있다. -레오나드 레빈

학습목표 P와 NP를 구별한다. Yes/No 문제와 최적화 문제의 차이를 이해한다. NP-완비의 의미를 이해한다.

문제의 종류 정지 문제 힐버트의 10번째 문제 … 풀 수 없는 문제들 (Unsolvable) (Undecidable) 여기에 속할 것이라고 강력히 추정! Presburger 산술 … 현실적인 시간내에 풀 수 없는 문제들 NP-완비 풀 수 있는 문제들 (Solvable) 최소 신장 트리 문제 최단 거리 문제 … (Decidable) 현실적인 시간내에 풀 수 있는 문제들

현실적인 시간 다항식 시간을 의미 비다항식 시간의 예 입력의 크기 n의 다항식으로 표시되는 시간 예: 3nk + 5nk-1 + … 비다항식 시간의 예 지수 시간 예: 2n 계승시간 예: n!

Yes/No 문제와 최적화 문제 Yes/No 문제 최적화 문제 예: 그래프 G에서 길이가 k 이하인 해밀토니안 경로가 존재하는가? 최적화 문제 예: 그래프 G에서 길이가 가장 짧은 해밀토니안 경로는 얼마인가? 두 문제는 동전의 앞뒷면

NP-Complete 이론 Yes/No 의 대답을 요구하는 문제에 국한 문제를 현실적인 시간에 풀 수 있는가에 관한 이론 그렇지만 최적화 문제와 밀접한 관계를 갖고 있다 문제를 현실적인 시간에 풀 수 있는가에 관한 이론 거대한 군을 이룸 이 중 한 문제만 현실적인 시간에 풀면 다른 모든 것도 저절로 풀리는 논리적 연결관계를 갖고 있다

현재까지의 연구결과 어떤 문제가 NP-Complete임이 확인되면 지금까지의 연구결과로는 이 문제를 현실적인 시간에 풀 수 있는 방법은 아직 없다 그렇지만 이 사실이 아직 증명은 되지 않음 클레이수학연구소의 21세기 7대 백만불짜리 문제 중의 하나 P=NP 문제

NP-Complete에 관한 비유 상사가 아주 어려운 문제를 해결하라고 지시했다 1. 나는 답을 구할 수가 없습니다. 아마 나는 멍청한 모양입니다.

2. 나는 답을 구할 수가 없습니다. 왜냐하면 이 문제는 답이 없어요.

NP-Complete 이론의 상황을 비유적으로 보여줌 3. 나는 답을 구할 수가 없습니다. 그렇지만 저렇게 수많은 천재들도 이 문제를 해결할 수 없습니다.

준비: 논리적 얼개 문제1: 정수 x=x1x2…xn은 3의 배수인가? 문제2: x1+x2+…+xn은 3의 배수인가? 쉽다 = 현실적인 시간에 풀 수 있다 문제1: 정수 x=x1x2…xn은 3의 배수인가? 문제2: x1+x2+…+xn은 3의 배수인가? 위 두 문제의 대답은 같다 Yes/No 대답이 일치한다 문제 2가 쉬우면, 문제 1도 쉽다

상황 문제 A도 쉬운가? 문제 B는 쉽다 문제 A는 Yes/No 대답이 일치하는 문제 B로 쉽게 변형된다 문제 A 쉽다 = 현실적인 시간에 풀 수 있다 문제 A 다항식 시간 변환 문제 B Yes Yes No No 문제 A도 쉬운가?

Poly-Time Reduction (다항식 시간 변환) 문제 A의 사례 α를 문제 B의 사례 β로 바꾸되 아래 성질을 만족하면 polynomial-time reduction이라 하고, 이를 α ≤ β 로 표기한다 변환은 다항식 시간에 이루어진다 두 사례의 답은 일치한다 p

문제 B의 대답이 Yes이면 Yes, No이면 No를 리턴한다 다항식 시간 변환 α β 문제 B를 푸는 알고리즘 Yes No 문제 A를 푸는 알고리즘 문제 A를 다항식 시간에 문제 B로 변환한다 변환된 문제 B를 푼다 문제 B의 대답이 Yes이면 Yes, No이면 No를 리턴한다 문제 B가 쉬운 문제라면 문제 A도 쉬운 문제이다

P와 NP P NP 어떤 문제가 NP임을 보이는 것은 대부분 아주 쉽다 Polynomial 다항식 시간에 Yes 또는 No 대답을 할 수 있으면 P NP Nondeterministic Polynomial Non-Polynomial의 준말이 아님! Yes 대답이 나오는 해를 제공했을 때, 이것이 Yes 대답을 내는 해라는 사실을 다항식 시간에 확인해줄 수 있으면 NP 어떤 문제가 NP임을 보이는 것은 대부분 아주 쉽다 NP-Complete 증명에서 형식적으로 확인하고 넘어가는 정도 ~11/12/2007

NP-Complete/Hard 다음 성질을 만족하면 문제 L은 NP-Hard이다 NP : Yes 대답이 나오는 해를 제공하면 이를 다항식 시간에 확인할 수 있으면 됨 다음 성질을 만족하면 문제 L은 NP-Hard이다 모든 NP 문제가 L로 다항식 시간에 변환가능하다 다음의 두 성질을 만족하면 문제 L은 NP-Complete이다 L은 NP이다. L은 NP-Hard이다. NP-Complete는 NP-Hard의 일부이므로 NP-Complete인 문제를 NP-Hard이라고 불러도 맞다 NP-Complete의 성질 1)은 대부분 자명하므로 핵심에 집중하기 위해 NP-Hard에 초점을 맞추자

정리 1 문제 L이 다음의 성질을 만족해도 NP-hard이다 알려진 임의의 NP- Hard 문제 A로부터 문제 L로 다항식 시간에 변환가능하다 Yes Yes 다항식 시간 변환 문제 L을 푸는 알고리즘 α β No No 문제 A를 푸는 알고리즘 만일 문제 L을 쉽게 풀 수 있다면, 문제 A도 쉽게 풀 수 있다 그러므로 모든 NP 문제를 쉽게 풀 수 있다

만일 문제 L이 쉬운 문제라면 문제 A도 쉬운 문제이다 다항식 시간 변환 α β 문제 L을 푸는 알고리즘 Yes No 문제 A를 푸는 알고리즘 만일 문제 L이 쉬운 문제라면 문제 A도 쉬운 문제이다 그러므로 모든 NP 문제도 쉬운 문제이다

NP-Hard 증명의 예 해밀토니안 싸이클 문제가 NP-Hard임은 알고 있다 가정 이를 이용해서 TSP 문제가 NP-Hard임을 보일 수 있다 해밀토니안 싸이클 - 그래프의 모든 정점을 단 한번씩 방문하고 돌아오는 경로 해밀토니안 싸이클 문제 - 주어진 그래프에서 해밀토니안 싸이클이 존재하는가?

해밀토니안 싸이클 문제의 instance(사례) A를 아래와 같이 TSP 문제의 instance B로 다항식 시간에 변환한다 1 변환 1 1 ∞ 1 1 해밀토니안 싸이클 문제의 instance TSP 문제의 instance Instance A가 해밀토니안 싸이클을 갖는다 Instance B가 길이 4 이하인 해밀토니안 싸이클을 갖는다 (그래프의 크기가 n이면 4 대신 n) 그러므로 TSP는 NP-Hard이다. Vertex 수와 일치

NP-Complete 문제의 초기 역사 GSAT ≤p ≤p SAT 3SAT ≤p ≤p CLIQUE SUBSET-SUM ≤p VERTEX-COVER ≤p ≤p ≤p HAM-CYCLE HAM-PATH HAM-PATH-2-POINTS ≤p TSP

직관과 배치되는 NP-Complete 문제의 예 Shortest path 그래프의 정점 s에서 t로 가는 shortest path는 간단히 구할 수 있다 Longest path 그래프의 정점 s에서 t로 가는 longest path는 간단히 구할 수 없다 NP-Complete 얼핏 비슷해 보이지만 위 두 문제의 난이도는 천지차이다! (지금까지의 연구 결과로는)

Longest Path 문제 두 점 사이 해밀토니안 경로 문제 주어진 그래프에서 vertex s에서 t로 가는 길이 k 이상인 simple path가 존재하는가? 두 점 사이 해밀토니안 경로 문제 주어진 그래프에서 정점 s에서 t에 이르는 해밀토니안 경로가 존재하는가? NP-Complete이라고 알려져 있음

두 점 사이 해밀토니안 경로 문제의 instance A로부터 Longest Path 문제의 instance B로 다항식 시간 변환 HAM-PATH-2-POINTS 문제의 instance LONGEST-PATH 문제의 instance 변환 1 Instance A가 두 점 s와 t사이에 해밀토니안 경로를 갖는다  Instance B가 두 점 s와 t 사이에 길이 4 이상인 (사실은 정확히 4) 단순 경로를 갖는다 (그래프의 크기가 n이면 4 대신 n-1) 그러므로 Longest Path 문제는 NP-Hard이다. 핵심에 집중하기 위해 성질 1은 일부러 누락. 추가로 성질 1을 증명해서 NP-Complete임을 보이는 것은 매우 간단하다.

CLIQUE 입력 질문 CLIQUE은 NP-Complete이다 그래프 G = (V, E), 양의 정수 K 그래프 G에 크기 K인 Complete subgraph가 존재하는가? CLIQUE은 NP-Complete이다 ~11/14/2007

3SAT CLIQUE임을 증명하기 위한 그림 ≤p ( x1 ∨ x2 ∨ x3 ) x1 x2 x3 x1 x2

NP 이론의 유용성 어떤 문제가 NP-Complete/Hard임이 확인되면 쉬운 알고리즘을 찾으려는 헛된 노력은 일단 중지한다 주어진 시간 예산 내에서 최대한 좋은 해를 찾는 알고리즘 (heuristic) 개발에 집중한다 Remind: 때로는 어떤 것이 불가능하다는 사실이 유용할 때도 있다. -- 레오나드 레빈

P와 NP의 포함 관계 P=NP NP P (b) (a) 위 (a)인지 (b)인지는 아직 밝혀지지 않음. 백만불의 상금이 걸려 있다.

NP와 NP-Complete, NP-Hard의 관계

Thank you