Ch.09 계산복잡도와 다루기 힘든 정도 (P & NP) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

From Garey & Johnson’s book I can’t find an efficient algorithm, I guess I’m just too dumb.

From Garey & Johnson’s book I can’t find an efficient algorithm, because the given problem is NOT possible to solve.

From Garey & Johnson’s book I can’t find an efficient algorithm, but neither can all these famous people.

현 시점에서 이 사원은 해당 문제에 대한 효율적인 알고리즘을 찾지도 못했고, 그러한 알고리즘이 불가능하다고 증명하지도 못했다. From our textbook 직장 상관이 어떤 문제에 대한 효율적인 알고리즘을 찾으라고 지시를 하였다. 많은 시간과 노력을 했음에도 불구하고 찾지 못했다. 그 결과를 상관에게 보고하였더니 해고를 당할 위험에 처해졌다. 그래서 상관에게 자신이 능력이 없는 것이 아니라 어쩌면 이 문제에 대해서는 효율적인 알고리즘이 존재하지 않을 수 있다는 것을 알린다. 상관은 이를 증명하라고 한다. 또 다시 많은 시간과 노력을 했음에도 불구하고 증명하는데 성공을 하지 못했다. (Continue…) 현 시점에서 이 사원은 해당 문제에 대한 효율적인 알고리즘을 찾지도 못했고, 그러한 알고리즘이 불가능하다고 증명하지도 못했다.

From our textbook 직장 상관이 어떤 문제에 대한 효율적인 알고리즘을 찾으라고 지시를 하였다. 그런데, 갑자기 몇몇의 위대한 전산학자 (Computer Scientist)들이 외판원 문제는 최악의 경우 시간복잡도가 지수시간 보다 좋은 알고리즘을 아직까지 발견되지 못했다는 사실을 기억해냈다. 더구나 지수시간 보다 좋은 알고리즘의 제작은 불가능하다고 증명한 사람도 아무도 없다. (Continue…)

From our textbook 직장 상관이 어떤 문제에 대한 효율적인 알고리즘을 찾으라고 지시를 하였다. [마지막 희망 !!!] 만약 “현재 풀고자 하는 문제에 대한 효율적인 알고리즘을 활용하면 외판원 문제에 대해서도 효율적인 알고리즘을 쉽게 만들어 낼 수 있다”는 사실을 증명할 수 있다면, 이는 위대한 전산학자들이 이루지 못한 것을 상관이 요구하고 있음을 뜻한다. 위와 같은 사실을 증명한 후 사원은 해고되는 대신 오히려 승진을 한다. 즉, 이 사원은 그 회사의 문제를 효율적으로 해결하는 알고리즘을 찾으려고 계속해서 노력하는 것은 신중하지 못한 선택이라는 것을 증명한 것이다.

From our textbook

그럼 이 장에서는 무엇을 배우는 걸까? 효율적인 알고리즘이란? 문제의 난이도 문제의 분류 다차시간(Polynomial-time) 알고리즘 문제의 난이도 다루기 힘든 정도 (Intractability) 문제의 분류 P, NP, NP-Complete, NP-Hard, NP-Easy, NP-Equivalent

다루기 힘든 정도 다차시간 알고리즘 (Polynomial-time Algorithm) 최악의 경우 시간복잡도의 상한이 입력 크기의 다항식인 알고리즘 즉, 입력 크기가 n이면, 다음을 만족하는 다항식 (Polynomial) p(n)이 존재한다. [예제 9.1] 최악의 경우 다음의 시간복잡도를 지닌 알고리즘은 모두 다차시간(Polynomial-time) 알고리즘이다. 최악의 경우 다음의 시간복잡도를 지닌 알고리즘은 모두 Polynomial-time 알고리즘이 아니다.    

다루기 힘든 정도 다루기 힘든 문제 (Intractable Problem) [Example] 연쇄행렬곱셈 문제 (3.4절)는 다루기 힘든 문제가 아니다. 무작정 알고리즘: 동적계획 알고리즘:    

다루기 힘든 정도 다루기 힘든 정도에 따른 문제의 분류 [분류 1] 다차시간 알고리즘이 발견된 문제 [분류 2] 다루기 힘들다고 증명된 문제 [분류 3] 다루기 힘들다고 증명되지 않았지만, 다차시간 알고리즘도 발견하지 못한 문제 [NOTE] 현재까지 발견된 수천 종의 문제 대부분은 분류 1이에 속하거나 분류 3에 속한다. [NOTE] 알고리즘이 다차시간인지 결정할 때 입력크기라는 것에 대해 주의를 기울일 필요 있다. (Chapter 9.2  Skip!, 각자 공부)

문제의 일반적인 분류 [분류 1] 다차시간 알고리즘을 찾은 문제 – 1/2 1) 다차시간 알고리즘을 처음부터 찾은 문제 정렬 문제: 합병정렬(Merge Sort), 퀵정렬(Quick Sort) 정렬된 배열에서의 검색 문제: 이분검색(Binary Search) 행렬곱셈 문제: 쉬트라센 알고리즘(Strassen Algorithm)      

문제의 일반적인 분류 [분류 1] 다차시간 알고리즘을 찾은 문제 – 2/2 2) 다차시간이 아닌 알고리즘도 있으나 결국 다차시간 알고리즘을 찾은 문제 연쇄행렬곱셈 문제: 동적 계획 방법의 알고리즘 최단 경로 구하기 문제: 동적 계획 방법을 사용하는 플로이드 (Floyd) 알고리즘 단일 지점 최단 경로 구하기 문제: 탐욕적인 방법을 사용하는 다익스트라 (Dijkstra) 알고리즘 최소비용 신장트리(Minimum spanning tree) 문제: 탐욕적인 방법을 사용하는 프림 (Prim), 쿠르스컬 (Kruskal) 알고리즘 등등…   [분류 1]에 속하는 문제는 P 집합에 속한다.

문제의 일반적인 분류 [분류 2] 다루기 힘들다고 증명된 문제 – 1/4 1) 비다항식(nonpolynomial) 크기의 결과를 요구하는 비현실적인 문제 모든 해밀토니안 회로 (Hamiltonian Circuit) 를 구하는 문제 : 만일 모든 정점들 간에 이음선이 있다면, (n-1)!개의 답을 얻어야 한다. 이러한 문제는 하나의 해밀토니안 회로를 구하는 문제에 비해서 필요이상으로 많은 답을 요구하므로 사실상 비현실적이고, 다루기 힘든 문제로 분류된다. 문제가 현실적으로 정의된 것이 아니다 (비상식적인 문제)

[분류 2]에 속하는 문제는 P 집합에도 NP 집합에도 속하지 않는다. 문제의 일반적인 분류 [분류 2] 다루기 힘들다고 증명된 문제 – 2/4 2) 요구가 현실적이지만, 다차시간에 풀 수 없다고 증명된 문제 (문제를 풀 수 있는 알고리즘 자체가 없다고 증명된 “결정 불가능한 문제 (undecidable problem)”) 종료 문제 (Halting Problem) : 임의의 알고리즘과 임의의 입력이 주어질 때, 그 알고리즘의 수행이 멈추는지를 결정하는 문제 Alan Turing 이 1936년 증명함 (다음 페이지 참조) 프레스버거 산술 문제 (Presburger Arithmetic Problem) : Fischer와 Rabin에 의하여 증명됨(1974) [NOTE] 놀랍게도 이런 부류에 속하는 문제는 상대적으로 별로 없다. [분류 2]에 속하는 문제는 P 집합에도 NP 집합에도 속하지 않는다.

문제의 일반적인 분류 [분류 2] 다루기 힘들다고 증명된 문제 – 3/4 Theorem: 종료 문제(Halting Problem)는 결정불가능한 문제이다. [Proof]: 종료 문제를 풀 수 있는 알고리즘이 존재한다고 가정하자. 그 알고리즘은 어떤 프로그램을 입력으로 받아서 그 프로그램이 종료하면 True를 반환하고, 종료하지 않으면 False를 반환할 것이다. 그 알고리즘을 Halt라고 하고, 다음과 같은 “Nonsense” 알고리즘을 만들어 보자. Nonsense() { if (Halt(Nonsense())) then while (true) do something; }

문제의 일반적인 분류 [분류 2] 다루기 힘들다고 증명된 문제 – 4/4 Theorem: 종료 문제는 결정불가능한 문제이다. [Proof]: 만일 “Nonsense” 알고리즘이 정상적으로 종료하는 알고리즘이라고 한다면, Halt(Nonsense())는 true가 되고, 따라서 이 알고리즘은 절대로 종료하지 않는다.  모순 발생 만일 “Nonsense” 알고리즘이 정상적으로 종료하지 않는 알고리즘이라고 한다면, Halt(Nonsense()) 는 false가 되고, 따라서 이 알고리즘은 종료하게 된다.  모순 발생 결론적으로, Halt라는 종료 문제를 푸는 알고리즘은 존재할 수 없다. Nonsense() { if (Halt(Nonsense())) then while (true) do something; }

문제의 일반적인 분류 [분류 3] 다루기 힘들다고 증명되지 않았고, 다차시간 알고리즘도 찾지 못한 문제 대부분의 문제가 이 분류에 속한다. 0 – 1 배낭채우기 (Knapsack) 문제 외판원 문제 (TSP) 부분집합의 합 구하기 문제 m 가지 색으로 그래프 색칠하기 문제 해밀토니안 회로 (Hamiltonian Circuit) 구하기 문제 등등… [분류 1], [분류 2], [분류 3]간에는 긴밀한 관계가 존재한다. 이제부터 이들 간의 관계를 공부한다. [분류 3]에 속하는 문제는 NP 집합에 속한다.

최적화 문제 vs. 결정 문제 최적화 문제(optimization problem) 결정 문제(decision problem) 최적의 해를 찾아야 한다. 결정 문제(decision problem) 대답이 “예“ 또는 “아니오”로 이루어지는 문제 이론을 전개하고 이해하기가 쉬움 문제 정의를 위해 추가 파라미터가 필요 [외판원문제] – 가중치가 있는 방향그래프에서 순환일주여행경로는 한 정점 에서 출발하여 다른 모든 정점들을 정확히 한번씩만 방문하고 다시 출발점으로 돌아오는 경로이다. 이 때... 외판원 최적화 문제: 순환일주여행경로 중 가장 길이가 짧은 순환일주 여행경로를 찾는 문제 외판원 결정 문제 (Travelling Salesman Decision Problem]: 임의의 양수 d가 주어지고, 이 d보다 길지 않은 순환일주여행경로가 있으면 “예“ 없으면 “아니오”로 대답하는 문제

최적화 문제 vs. 결정 문제 0-1 배낭채우기 최적화 문제 – 최대 용량이 W인 배낭에 넣을 아이템의 무게와 가치를 안다고 가정하고, 가치의 합이 최대가 되도록 아이템을 배낭에 어떻게 채울지 알아내는 문제 0-1 배낭채우기 결정 문제 – 임의의 총 가치액수인 P가 주어지고, 최대 용량이 W인 배낭에 넣을 아이템의 무게와 가치를 안다고 가정하고, 가치의 합이 최소한 P가 되도록 아이템을 배낭에 채울 수 있다면 “예“ 없으면 “아니오”로 대답하는 문제 그래프 색칠하기 최적화 문제 – 인접한 두 정점이 같은 색이 되지 않도록 그래프를 색칠하는 데 필요한 색의 최소 가지수를 구하는 문제 그래프 색칠하기 결정 문제 – 임의의 양의 정수 m이 주어지고, 최대한 m가지 색을 사용하여 인접한 두 정점이 같은 색이 되지 않도록 그래프를 색칠할 수 있다면 “예“ 없으면 “아니오”로 대답하는 문제

최적화 문제 vs. 결정 문제 최적화 문제와 결정 문제의 상관관계 [분류 3]에 속한 모든 문제에 대해 최적화 문제, 결정 문제 모두 아직 까지 다차시간 알고리즘을 발견하지 못하였다. 임의의 최적화 문제에 대한 다차시간 알고리즘이 있으면 그에 상응하는 결정 문제에 대한 다차시간 알고리즘도 쉽게 만들 수 있다. [Example] 외판원 최적화 문제를 해결하는 다차시간 알고리즘을 통해 얻은 일주경로의 길이가 120이면, 외판원 결정 문제에서 d가 120보다 큰 값이라면 주어진 외판원 결정 문제의 답은 “예”이고 120보다 작거나 같은 값이라면 주어진 외판원 결정 문제의 닶은 “아니오”가 된다. 이후부터 여러가지 이론을 전개하고 이해하기가 쉬운 결정 문제만을 다룬다.

집합 P와 집합 NP 집합 P (Polynomial) P는 다차시간 알고리즘으로 풀 수 있는 모든 결정 문제들의 집합이다. 아직까지 아무도 이 문제는 푸는 다차시간 알고리즘을 만들지 못했다. 하지만, 이 문제를 다차시간 알고리즘으로 풀 수 없다고 증명도 못했다. (정확한 답) Maybe, Maybe not, Nobody knows yet. [분류 3]에 속한 모든 문제(NP에 속한 문제들)들도 이와 같은 상황이 똑같이 적용된다.

집합 P와 집합 NP 검증 (Verification) 임의의 결정 문제의 어떤 사례 (어떠한 파라미터)에 대한 답이 “예”라고 알고 있다고 주장하는 사람이 있다고 하자. 이 때, 그 사람이 “예”라는 결정을 내리기 위해 만든 최적화 문제의 답이 유효한 답인지 증명할 수 있는 절차 예를 들어, 외판원 결정 문제의 답을 “예”라고 주장하는 사람이 만든 일주여행경로가 주어졌을 때, 그 경로가 과연 그런지를 위와 같은 verify 함수를 통해 확인할 수 있다. boolean verify(Weighted-digraph G, Number d, Claimed-tour S) { if (S is a tour && the total weight of the edges in S <= d) return true; else return false;

집합 P와 집합 NP 검증 (Verification) 이 검증 절차는 분명히 다차시간 안에 수행될 수 있다. 위 검증은 d보다 작은 일주여행경로를 찾는 것이 아니다. 위 검증은 일주여행경로 S가 d라는 파라미터를 지닌 결정 문제의 해답으로서 “예”임을 증명할 수 있는지 다차시간에 검증하는 용도로 사용된다. 결정 문제에 대한 답을 다차시간에 확인할 수 있는 특성을 다차시간 검증가능성(polynomial-time verifiability)이라 한다. boolean verify(Weighted-digraph G, Number d, Claimed-tour S) { if (S is a tour && the total weight of the edges in S <= d) return true; else return false;

집합 P와 집합 NP 비결정적 알고리즘 (Nondeterministic Algorithm) 임의의 결정문제에 대해 다음과 같은 두 가지 단계로 구성된 알고리즘 1) 추측(비결정적-nondeterministic) 단계: 결정 문제의 사례(임의의 파라미터)가 주어지면 임의의 방법 (예를 들어, Guessing)에 의해 임의의 가능한 해답 S를 만든다. S는 그 사례에 대한 해답으로 추측한 것으로서 무의미하게도 생성 가능 2) 검증(결정적) 단계: 결정 문제의 사례와 S를 입력받아, 다음 세 가지 중 하나와 같이 동작한다. 경우 1. “true”를 출력하고 종료  S가 올바른 해답 경우 2. “false”를 출력하고 종료 (Optionally 경우 3) 종료하지 않는다 (예를 들어, 무한 루프에 빠짐) (경우 2와 경우 3은 S가 올바른 해답으로 확인되지 않은 경우)

집합 P와 집합 NP 비결정적 알고리즘 (Nondeterministic Algorithm) 앞서 보았던 verify 함수는 위와 같은 비결정적 알고리즘의 검증 단계에서 활용할 수 있는 함수이다. 결정 문제를 풀기 위하여 실제로는 비결정적 알고리즘을 사용하지는 않는다. 하지만, 다음과 같은 경우에는 (이론적으로) 비결정적 알고리즘이 결정 문제를 “푼다(Solve)”고 한다. 임의의 사례에 대해, 검증단계가 true를 반환하는 문자열 S가 존재  “예” 임의의 사례에 대해, 검증단계가 true를 반환하는 문자열 S가 존재 않지 않음  “아니오”

집합 P와 집합 NP 비결정적 알고리즘 (Nondeterministic Algorithm) [Example] 외판원 결정 문제에 대한 비결정적 알고리즘 문제의 사례: 주어진 방향 가중치 그래프 & d = 15 다차시간 비결정적 알고리즘 (Polynomial-time Nondeterministic Algorithm) 검증단계가 다차시간 알고리즘인 비결정적 알고리즘

집합 P와 집합 NP 집합 NP (Nondeterministic Polynomial) 다차시간 비결정적 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합 즉, 임의의 결정 문제가 NP에 속하기 위해서는 반드시 다차시간에 검증을 할 수 있는 알고리즘이 존재하여야 한다. 하지만, 해당 결정 문제 자체를 해결할 수 있는 다차시간 알고리즘이 존재해야 함을 의미하지는 않는다. 어떤 결정 문제를 풀 수 있는 다차시간 알고리즘을 찾을 수 없을 때, 다차 시간 비결정적 알고리즘을 찾으면 그 문제는 NP에 속한다. [주의] NP가 Non-Polynomial의 준말이 아님!

집합 P와 집합 NP 집합 NP (Nondeterministic Polynomial) [Example] 외판원 문제 그러면 모든 가능한 일주여행경로를 다차시간 비결정적 알고리즘을 통하여 검사하면 원래 주어진 결정 문제가 해결 되지 않을까? 모든 정점 간에 간선이 있으면 총 (n-1)!개의 일주여행경로가 존재한다. 따라서 다차시간에 그 결정문제를 해결할 수 없다. 이 외에도 [분류 3]에 속하는 모든 문제는 NP에 속한다. (사색…) 어떤 결정 문제가 주어졌을 때, 그 문제가 NP에 속함을 어떻게 증명할까?

P는 아니면서 NP에만 존재한다고 증명된 문제는 없다. why? 검증 단계에서 P에 속한 문제를 해결하는 다차시간 알고리즘을 수행한다. NP에 속하지 않는 문제 = 다루기 힘들다고 증명이 된 문제 [분류 2]에 속한 문제 이러한 문제들은 상대적으로 거의 없다. 과연 NP가 P를 “진”부분집합으로 포함하는가? NP에 속하면서 P에 속하지 않는 문제가 존재한다고 증명한 사람은 아무도 없다. 모든 결정 문제 [분류 2]에 속한 문제들 P는 아니면서 NP에만 존재한다고 증명된 문제는 없다.

P는 아니면서 NP에만 존재한다고 증명된 문제는 없다. 모든 결정 문제 [분류 2]에 속한 문제들 P는 아니면서 NP에만 존재한다고 증명된 문제는 없다. 집합 NP 에 관한 고찰 P  NP 인가? (NP – P   인가?) P = NP 인가? (NP – P =  인가?) 위의 질문은 Computer Science에서 가장 유명하고 복잡한 질문 중 하나이다.

집합 P와 집합 NP 집합 NP 에 관한 고찰 만약 P = NP 라면, 그래서, 그러한 결정문제들에 대한 다차시간 알고리즘을 찾는 문제는 의미가 있는 작업이다. 즉, 사원은 상사에게 받은 문제를 효율적으로 풀기 위해 계속 노력해야 한다. 사실 많은 사람들이 P  NP일 것 이라고 생각하고 있기는 하지만 아무도 이것을 증명하지 못하고 있다. ( 해당 문제를 못 찾았다.)

P = NP 증명의 어려움 P  NP 를 증명하기 위해서는…? P = NP 를 증명하기 위해서는…? 즉, 외판원 결정 문제가 다차시간 알고리즘이 존재하지 않음을 증명하면 된다. P = NP 를 증명하기 위해서는…? NP에 속한 모든 문제에 대해 다차시간 알고리즘을 찾아야 한다. 이는 상당히 진부한 작업이 되며 NP에 속한 문제는 계속해서 발견될 것이기 때문에 무한정 이러한 다차시간 알고리즘을 개발해야 한다. 이 증명을 간략화시킬 수 있을까?

CNF 만족가능도 결정 문제  

NP-Complete CNF-만족가능도 결정 문제의 예

CNF 만족가능도 결정 문제가 P에 속한다면 P=NP이다. NP-Complete CNF-만족가능도 결정 문제의 특성 이 문제는 NP에 속함이 증명되었다. 하지만 아무도 이 문제를 푸는 다차시간 알고리즘을 찾지도 못하고, 아무도 이 문제를 다차시간에 풀 수 없다고 증명하지도 못했다. 따라서, 이 문제가 P에 속할지도 모른다. 1971년 Stephen Cook이 증명한 명제 CNF 만족가능도 결정 문제가 P에 속한다면 P=NP이다.

변환 (Transformation) 알고리즘 B 결정 문제를 해결하는 다차시간 알고리즘을 알고 있다. A 결정 문제의 모든 사례에 대해 이것과 대응되는 B 결정 문제의 사례를 만드는 다차시간 알고리즘이 있다. 이 알고리즘을 변환 (Transformation) 알고리즘이라고 한다. 여기서 대응된다는 것은 B 를 푸는 알고리즘이 y에 대해 “예”라고 답하면 문제 A를 푸는 알고리즘도 x에 대해 “예”를 답하는 것을 의미 다차시간 변환 알고리즘으로서 tran 함수를 구할 수 있으면 A도 다차시간에 해결할 수 있다. y=tran(x)

변환 (Transformation) 알고리즘 [정의] 다차시간 다일 변환가능 (polynomial-time many-one reducible) = 다차시간 다일 축약 결정 문제 A를 결정 문제 B로 변환하여 주는 다차시간 변환 알고리즘이 존재하면 문제 A는 문제 B로 다차시간 다일 변환가능 (polynomial-time many-one reducible)하다고 말한고, 기호로는 “A∝B”와 같이 표기한다. 다일(many-one)이란 변환 알고리즘이 A의 여러 사례를 B의 한 사례로 매핑할 수 있기 때문이다. [정리 9.1] 임의의 결정 문제 B가 P에 속하고 A∝B이면 A는 P에 속한다.

집합 NP-Complete [정의] 다음 두 가지가 만족되면 문제 B는 NP-Complete에 속한다. NP에 있는 모든 문제 A에 대해 A ∝ B이다. 위의 정의를 사용한 임의의 문제에 대한 NP-Complete 판단 어떤 문제가 NP-Complete인지를 위의 정의에 근거해서 증명하는 작업은 매우 어렵다. 왜냐하면 NP에 속한 모든 문제가 그 문제로 변환가능(reducible)하다는 것을 보여야 하기 때문이다. 그러나 다행스럽게도, 1971년 Cook이 다음 두 개의 정리를 증명했다.

집합 NP-Complete [Cook의 정리 1] CNF 만족가능도 문제는 NP-Complete에 속한다. [Cook의 정리 2] 다음 두 가지가 만족되면 문제 C는 NP-Complete에 속한다. C는 NP에 속한다. 임의의 NP-Complete 문제 B에 대해 B ∝ C이다. Cook의 정리 1, 2의 의미 (1) 임의의 문제 C가 NP에 속하고, (2) CNF 만족가능도 문제 또는 다른 NP-Complete 문제를 문제 C로 변환가능함을 보인다면, 결국 문제 C가 NP-Complete에 속한다는 것을 증명할 수 있다.

집합 NP-Complete 해밀톤 회로 결정 문제 (P. 388) 외판원 (비방향) 결정 문제 (P.389) (2) CNF-만족가능도문제 ∝해밀톤 회로 결정 문제 그러므로, 해밀톤 회로 결정 문제는 NP-Complete에 속한다. 외판원 (비방향) 결정 문제 (P.389) (1) 외판원 (비방향) 결정 문제는 NP에 속한다. (2) 해밀톤 회로 결정 문제 ∝외판원 (비방향) 결정 문제 그러므로, 외판원 (비방향) 결정 문제는 NP-Complete에 속한다.

집합 NP-Complete 외판원 결정 문제 (P.390) (2) 외판원 (비방향) 결정 문제 ∝ 외판원 결정 문제 그러므로, 외판원 결정 문제는 NP-Complete에 속한다. 외판원 문제뿐만 아니라 0-1 배낭 채우기 문제, m-색칠하기 문제 등은 모두 NP 문제이면서 동시에 NP-Complete 문제 이다.

문제와 변환에 관한 논리적 개념 문제1: 정수 x=x1x2…xn은 3의 배수인가? 위 두 문제의 대답은 같다 Yes/No 대답이 일치한다 문제 2가 쉬우면(어려우면), 문제 1도 쉽다(어렵다) 상황 문제 B는 쉽다 (어렵다) 문제 A는 Yes/No 대답이 일치하는 문제 B로 쉽게 변형된다 문제 A 다항식 시간 변환 문제 B Yes Yes No No

문제와 변환에 관한 논리적 개념 문제 A를 다항식 시간에 문제 B로 변환한다 변환된 문제 B를 푼다 다항식 시간 변환 α β 문제 B를 푸는 알고리즘 Yes No 문제 A를 푸는 알고리즘 문제 A를 다항식 시간에 문제 B로 변환한다 변환된 문제 B를 푼다 문제 B의 대답이 Yes이면 Yes, No이면 No를 리턴한다 문제 B가 쉬운(어려운) 문제라면 문제 A도 쉬운(어려운) 문제이다

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (1/6) 만약 NP-Complete 에 속한 임의의 문제가 P에도 속한다면 NP-Complete의 정의와 정리 9.1 (PPT Page 39) 때문에 NP에 속한 모든 문제들도 P에 속한다. 즉 NP=P가 된다. [Proof] 임의의 문제 B가 P와 NP-Complete에 동시에 속한다. NP-Complete의 정의에 의해 임의의 NP 문제 A는 A ∝ B가 성립한다. 정리 9.1에 의해 NP 문제 A는 P에 속한다.

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (2/6) 외판원 문제뿐만 아니라 0-1 배낭 채우기 문제, m-색칠하기 문제 등은모두 NP 문제이면서 동시에 NP-Complete이다. 이들의 최악 시간복잡도는 모두 다르지만 다음과 같은 측면에서 등가(equivalent)이다. 이들 중 한 문제가 P에 속한다고 증명되면 다른 문제들도 모두 P에 속해야 한다. 이런 문제들을 NP-complete 문제라 한다.

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (3/6) 종료 문제, 프레스버거 산술 문제 등은 NP에도 속하지 않으므로 NP-Complete에도 속하지 않는다. P=NP 라면 다음과 같이 그림을 그릴 수 있다. P (=NP)에 있긴 하지만 NP-Complete에 속하지 않는 문제 언제나 “예”를 돌려주는 아주 사소한 결정 문제는 NP-Complete 정의에 따라 NP-Complete에 속하지 않는다. 사소하지 않은 (어느 정도로 복잡한) 결정 문제는 사소한 결정 문제로 변환이 불가능하다.

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (4/6) PNP 라면 다음과 같이 그림을 그릴 수 있다. 즉, 다음과 같은 등식이 성립한다. 그렇다면, PNP 일 때 다음 집합에 속하는 문제가 존재할까? P  NP-Complete =  NP – (P  NP-Complete)

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (5/6) 그래프 동형성 (Graph Isomorphism) 문제 교재 Page 391 참조 NP에 속함은 증명되었다. 이 문제에 대한 다차시간 알고리즘을 아직까지 발견하지 못했다. 그러므로, P에는 속하지 않는다. NP-Complete에 속함도 아직 증명하지 못했다. 즉, B ∝ 그래프 동형성 문제를 만족하는 임의의 NP-Complete 문제 B 존재를 밝히지 못했다. 따라서, 이 문제가 P에 속하는지 NP-Complete 에 속하는지 알지 못한다.

집합 NP-Complete의 고찰 집합 NP-Complete에 대한 고찰 (6/6) PNP이면 반드시 P도 아니고 NP-Complete도 아닌 문제가 존재한다는 것은 증명되었다. Ladner의 논문 (1975년) - Page 392 참조 그렇다고, 그래프 동형성 문제가 P도 아니고 NP-Complete도 아닌 NP 문제라고 증명된 것은 아니다.

집합 NP-Hard [정의] 문제 B를 해결하여 주는 가상의 다차시간 알고리즘으로 문제 A를 해결할 수 있으면 문제 A는 문제 B로 다차시간 튜링 변환가능(polynomial-time Turing reducible)하다고 말한다. 기호로는 “A ∝T B”와 같이 표기한다. 위와같은 가상의 다차시간 알고리즘 (또는 기계)를 어떤 문헌에서는 Oracle 이라고도 한다. A와 B가 결정 문제이면, 다음이 성립한다. A ∝ B implies A ∝T B

집합 NP-Hard [정의] 임의의 NP-complete 문제 A에 대해 A ∝T B이면 문제 B는 NP-Hard라 한다. [proof] – 교재 P.395 주어진 문제인 외판원 최적화 문제는 B로 표기하고, B를 해결하는 가상의 다차시간 알고리즘을  라고 가정하자. NP-Complete 문제인 A로서 외판원 결정 문제를 정하고 A ∝T B 을 다음과 같이 증명한다. 임의의 그래프 G에 대해  를 사용하여 B 문제를 풀어서 최적의 경로 및 mindist를 구한다. 임의의 양의 정수 d에 대해 A 문제는 mindist  d 임을 판단하는 것은 다차시간 내에 결정할 수 있다. 그러므로, A ∝T B 이다.

NP-Complete vs. NP-Hard [Cook의 정리 2 – PPT p.41] 다음 두 가지가 만족되면 문제 B는 NP-Complete에 속한다. B는 NP에 속한다. 임의의 NP 문제 A에 대해 A ∝ B이다. 고찰 임의의 NP-Complete 문제가 문제 B로 다항식 시간에 변환가능하면, 문제 B는 NP-Hard에 속한다. 그러므로, 다음의 두 성질을 만족하면 문제 B는 NP-Complete이다 B는 NP이다. B는 NP-Hard이다. 어떠한 문제가 NP-Complete임을 증명할 때 첫 번째 조건은 대부분 자명하므로 핵심에 집중하기 위해 NP-Hard 조건에 일반적으로 초점을 맞춘다. 문제 B가 NP-Hard에 속할 조건이라고 일반적으로 칭함

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

NP와 NP-Complete, NP-Hard의 관계 추정되는 관계 (Source: 교재)

NP와 NP-Complete, NP-Hard의 관계 추정되는 관계 1, 관계 2 (Source: Wikipedia)

[참고 문헌] Wiki 한국판 사이트에서… 클레이 수학연구소 (Clay Mathematics Institute, CMI)의 소개 www.claymath.org 밀레니엄 문제 (Millennium Prize Problem) 상금 100만달러 문제들… P-NP 문제는 Millennium Prize Problem 중 하나이다.