decision problem 과 optimization problem 의 관계 (feat. np)

optimization problem 에 대해 배우는 최적화 수업과 decision problem 의 다양한 구분들 (p, np)에 대해 배우는 알고리즘 수업을 동시에 듣다가 optimization 문제를 decision problem 으로 바꿀 수 있다는 사실을 알게되었다. 

 

예를들어 traveling salesperson problem (TSP) 문제를 최적화 문제로 말한다면 우리는 모든 도시를 방문하는 최소 경로를 구하고 싶다고 할 수 있다. 이걸 decision problem 으로 바꾸면 어떨까? 참고로 decision problem 은 YES/NO로 답을 내릴 수 있는 문제를 의미한다. 모든 도시를 방문하면서 최대 k거리를 갖는 경로가 있을까? 로 바꿀 수 있다. 만약 decision problem 을 다항 시간 내에 구할 수 있다면, 우리는 k를 작은수부터 큰수로 차례로 늘려가면서 YES 였던 답이 NO로 바뀌는 순간을 찾을 것이고 NO로 바뀌는 가장 직전 k가 바로 최대값이다. 이걸 조금 더 효율적으로 하고싶다면 binary search 를 이용하면 된다. 

 

이 예시를 보고 다음과 같은 의문들이 떠올랐고 교수님께 여쭤봐서 대답을 들었다. 

1. 만약 decision problem 이 P이면 (다항시간 안에 풀 수 있다면) 그 문제의 optimization problem 은 항상 P 일까? 

일반적으로 decision problem을 풀 수 있다면 optimization problem 도 풀 수 있음을 보일 수 있는 경우가 많다. 하지만 해가 존재함을 보이는게 항상 그것을 찾을 수 있다는 사실을 의미하는 것은 아니다. Binary search 가 많은 경우에 도움이 되지만 항상 그렇지만은 않다. (*For example, testing primality is known to be in P, but it is not known how to factor composite numbers in polynomial time.) 각각의 문제에 특화된 search 방식을 항상 찾아야하며 모든 문제에 적용가능한 일반적인 방식은 알려져 있지 않다. 

 

2. 왜 np 는 애초에 decision problem 에서만 정의되어야할까? polynomial time 안에 풀 수 없다, 있다는 optimization 문제에서도 똑같이 적용될 수 있는게 아닐까? 

애초에 complexity theory 가 decision problem 에서 발전 된 것이기 때문. 다른 종류의 문제 (counting problems, computing values of functions, optimization problems)에서는 각각의 문제에 특화되어 문제의 복잡도를 파악하기 위한 다른 이론이 발전되어왔다.