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

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

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

그럼 이 장에서는 무엇을 배우는 걸까? 효율적인 알고리즘이란? 문제의 난이도 문제의 분류 다차시간(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 참고)

문제의 일반적인 분류 [분류 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)!개의 답을 얻어야 한다. 이러한 문제는 하나의 해밀토니안 회로를 구하는 문제에 비해서 필요이상으로 많은 답을 요구하므로 사실상 비현실적이고, 다루기 힘든 문제로 분류된다. 문제가 현실적으로 정의된 것이 아니다 (비상식적인 문제) [note] 만약 해밀토니안 회로를 하나만 요구하는 문제라면 분류 2에 속하지 않는다.

[분류 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 종료 문제(Halting Problem) - 임의의 알고리즘과 임의의 입력이 주어질 때, 그 알고리즘의 수행이 멈추는지를 결정하라 Theorem: 종료 문제(Halting Problem)는 결정불가능한 문제이다. [Proof]: 종료 문제를 풀 수 있는 알고리즘을 구현한 isHalt() 함수가 존재한다고 가정하자. 이 때 isHalt() 함수는 어떤 프로그램을 입력으로 받아서 그 프로그램이 종료하면 True를 반환하고, 종료하지 않으면 False를 반환한다. 다음에, 다음과 같은 “Nonsense” 알고리즘을 다음은 함수를 만들어 보자. Nonsense() { if (isHalt(Nonsense())) then while (true) do something; }

문제의 일반적인 분류 [분류 2] 다루기 힘들다고 증명된 문제 – 4/4 Theorem: 종료 문제는 결정불가능한 문제이다. [Proof]: 만일 “Nonsense” 알고리즘이 정상적으로 종료한다면, isHalt(Nonsense())는 true가 되고, 따라서 이 알고리즘은 절대로 종료하지 않는다.  모순 발생 만일 “Nonsense” 알고리즘이 정상적으로 종료하지 않는다면, isHalt(Nonsense()) 는 false가 되고, 따라서 이 알고리즘은 종료하게 된다.  모순 발생 결론적으로, isHalt라는 종료 문제를 푸는 알고리즘은 존재할 수 없다. Nonsense() { if (isHalt(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 함수는 위와 같은 비결정적 알고리즘의 검증 단계에서 활용할 수 있는 함수이다. TSP와 같은 결정 문제를 풀기 위하여… 실제로는 비결정적 알고리즘을 사용하지는 않는다. 하지만, 다음과 같은 경우에는 (이론적으로) 비결정적 알고리즘이 결정 문제를 “푼다(Solve)”고 한다. 임의의 사례(파라미터)에 대해, 검증단계에서 해답 S가 true를 반환  “예” 임의의 사례(파라미터)에 대해, 검증단계에서 해답 S가 false를 반환  “아니오”

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

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

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

P는 아니면서 NP에만 존재한다고 증명된 문제는 없다. why? 검증 단계에서 P에 속한 문제에 대한 해답 S가 올바른 답인지 결정하는 다차시간 알고리즘은 어렵지 않게 만들 수 있다. 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에서 가장 유명하고 복잡한 질문 중 하나이다. Millennium Prize Problems https://en.wikipedia.org/wiki/Millennium_Prize_Problems

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

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