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

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

NP-완비에 관한 비유 상사가 아주 어려운 문제를 해결하라고 지시했다

NP-완비 이론의 상황을 비유적으로 보여줌

다항식 시간 변환 준비 문제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도 쉬운가?

다항식 시간 변환 문제 A의 사례 α를 문제 B의 사례 β로 바꾸되 아래 성질을 만족하면 다항식 시간 변환이라 하고, 이를 α ≤ β 로 표기한다 변환은 다항식 시간에 이루어진다 두 사례의 답은 일치한다 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-완비 증명에서 형식적으로 확인하고 넘어가는 정도

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

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

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

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

NP-완비 문제의 초기 역사 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-완비 문제의 예 최단경로 최장경로 그래프의 정점 s에서 t로 가는 최단경로는 간단히 구할 수 있다 얼핏 비슷해 보이지만 위 두 문제의 난이도는 천지차이다! (지금까지의 연구 결과로는)

최장경로 문제 주어진 그래프에서 vertex s에서 t로 가는 길이 k 이상인 단순경로가 존재하는가? 두 점 사이 해밀토니안 경로 문제 주어진 그래프에서 정점 s에서 t에 이르는 해밀토니안 경로가 존재하는가? NP-완비

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

CLIQUE(완전 부분 그래프 문제) 입력 질문 CLIQUE은 NP-완비다 그래프 G = (V, E), 양의 정수 k 그래프 G에 크기 k인 완전 부분 그래프가 존재하는가? CLIQUE은 NP-완비다

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

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

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

NP와 NP-완비, NP-하드의 관계 NP-하드 NP NP-완비 P P 부분은 추정

Thank you