NP hard 문제에 대한 접근법

대부분의 discrete optimization problem 은 NP-hard 이다. 만일 P!=NP 일 경우에 우리는 NP-hard 문제를 (1) 다항 시간 내에 (2) 모든 인스턴스(예제 문제)에 대해서 (3) 최적값을 구할 수 있는 알고리즘을 찾아낼 수 없을 것이다. 

그래서 연구자들이 택하는 접근법은 종종 세가지 조건중 하나를 완화하여 접근한다.

첫째로 다항 시간 조건을 완화한다면 어떻게 최적해를 더 효율적으로 탐색해나갈지 고민하는것에 집중해볼 수 있다. 하지만 이 경우 어떤 인스에 대해 수 분에서 수십 시간 안에 최적해를 구해내는데 성공했다 할지라도 바로 다음 예제의 최적해를 합리적 시간안에 구해낼 것이라 장점할 수 없는 것이 가장 큰 문제이다.

두번째로 모든 instance 에 대해 일반적으로 적용될 알고리즘을 개발하겠다는 목표를 완화한다면 우리는 아주 특별한 경우에만 적용되는 알고리즘을 개발해볼 수 도 있다. 그 특별한 경우가 현실세계에서 자주 등장하는 문제라면 이 접근법이 유용하겠지만, 그런 케이스는 드물다.

세번째로는 최적해를 찾는다는 조건을 완화해볼 수 있다. 충분히 좋은 해를 다항시간안에 찾는 것을 목표로 할 수 있다. 종종 이런 알고리즘들은 몇 초 안에 해를 찾아주며 heuristics/metaheuristics 혹은 alpha-approximation 알고리즘이 이에 해당한다.