NP Complete
-
알고리즘 ch13 NP-complete Problems학교 수업/알고리즘 2020. 6. 16. 17:56
Optimization problem : 최적의 답를 찾는 문제 ex) shortest pathDecision problem : 답이 yes or no 인 문제 Class P - 어떤 decision 문제에 대해 polynomial time에 그 문제에 대한 해결법을 찾아낼 수 있다면, 그 문제는 클래스 P에 속한다. 즉, 다항시간내에 풀 수 있는 decision 문제들의 class를 class P라고 한다. 다항시간(polynomial time) : O(n^k) 다항시간내에 풀 수 있는 문제들은 tractable하다고 한다.문제의 어떤 알고리즘이 다항시간내에 풀린다면 efficient 알고리즘이라고 한다. Class NP- 어떤 문제가 non-deterministic polynomial time alg..