[Algorithm] NP-completeness : NP-완전문제, Non-deterministic Polynomial time, 비결정론적 다항시간 문제, 난해문제

일단 이름이 짜증 난다. NPC라고도 불리는 Nn Polynomial time completeness problem ( NP-완전 문제 ) 는 쉽게 말해서 컴퓨터로 돌려서 결과를 얻는 데 며칠이 걸릴지 모르는 문제다. 그런데 심지어 어떤 문제가 NPC 문제인 지 아는 것도 쉽지 않다.  빠른 해답이 알려지지도 않았기 때문에 정확한 답을 찾아내기 힘들다. 그나마 다행인 게 근사 알고리즘을 통해 비슷한 결과를 꺼내는 것으로 대체 가능하다는 정도일까.

 

대표적인 예시로 외판원 문제가 있다. 도시를 돌아다니며 방문판매를 하는 외판원이 도시를 돌아다닐 수 있는 모든 경우의 수를 나타내고자 할 때의 시간 복잡도는 O(n!) 이다. 도시 2개나 3개 정도까지는 파악하는 데 오래 걸리 지 않지만, 도시가 10개만 되어도 3628800 가지의 경로가 나온다. 새삼스럽게 O(n^2) 의 시간 복잡도 정도면 엄청 양호한 걸로 여겨진다.

 

또 다른 대표적인 NP 완전 문제는 집합 커버링 문제이다.

집합이라는 용어는 접할 때마다 쉽다는 생각과 어렵다는 생각이 공존하는 단어인 거 같다

 

한국에 좀비 사태가 터져서 라디오 방송을 해야 한다고 생각해보자.

사용 가능한 라디오 기지국은 아래의 이미지와 같다.

생각보다 많은 라디오 기지국이 남은 것 같은 기분이지만 여하튼

딱 보기에도 여러 지역을 동시에 커버하는 기지국이 많은 걸 확인할 수 있다.

 

밖에는 좀비가 우글거리기 때문에, 최소한의 동선으로 최소한의 기지국만 선택해서 방송을 하려고 한다.

어떤 선택이 최선의 선택이 될까?

 

아마 나라면, 가장 넓은 범위를 커버하는 라디오 기지국을 선택하고, 어딘가 빠지는 곳이 생기는 경우 그 부분을 해결하는 방향으로 방문해야 할 기지국을 선택할 것이다. 또, 누군가는 지역별 인구수에 초점을 맞춰서 우선순위를 결정할 수도 있다.

 

그렇다면 먼저 내 방식대로 기지국을 선택해보자.

 

가장 넓은 범위를 커버하는 라디오 기지국을 순서 없이 골라보자.

 

• 서울 ( 경기도 전역과 충청도, 강원도 일부를 포함 )
• 부산 ( 경남 전역과 경북 일부를 포함 )
• 광주 ( 전남 전역과 전북 대부분을 포함 )
• 제주 ( 제주까지 닿는 기지국은 제주뿐임 )
• 강릉 ( 강원도 전역과 서울, 부산으로 커버되지 않은 지역을 커버할 수 있음 )
• 대전 ( 충청도 전역과 남아있는 경북 일부를 커버할 수 있음 )

이렇게 9 곳의 라디오 기지국 중에서 6개의 지역을 선택하였다.

만약 기지국의 선택 방식을 인구 밀집도에 초점을 맞춰서 순서대로 우선순위를 결정한다면 아래와 같을 것이다.

1. 서울 ( 수도권 2천만 )
2. 부산 ( 경상권 13백만 )
3. 대전 ( 충청권 5.5백만 )
4. 광주 ( 전라권 5.1백만 )
5. 강릉 ( 강원권 1.5백만 )
6. 제주 ( 60만 )

결국 선택된 지역을 보면 같은 결과를 보인다. 왜 그럴까?

이 문제는 어떤 지역이 우선순위가 높은지 낮은 지를 따지지 않는다. 단지 모든 지역을 커버해야 하기 때문에 최대한 넓은 지역을 포함하거나 다른 기지국이 커버하지 못하는 특정 구역을 커버할 수 있는 곳이 포함되기 때문이다.

 

NP-완전 문제는 이와 같이 근사 알고리즘을 통해서 하나의 기준을 토대로 하나씩 채워가는 방법으로 해결한다.

 

대개의 경우 아래와 같은 때에 NP-완전 문제로 본다. ( 물론 항상 예외는 있고, 아래의 경우도 참고 사항이다 )

• 항목이 적을 때에는 알고리즘이 빠른데, 항목이 늘어나면서 급격히 느려집니다
• 'x의 모든 조합'이라고 하면 대개 NP-완전 문제입니다
• 더 작은 하위 문제로 변환할 수 없어서 X의 가능한 모든 버전을 계산해야 한다면 아마도 ( ? ) NP-완전 문제일 겁니다
• 문제가 수열 ( 외판원 문제와 같은 도시의 순서같이 ) 을 포함하고 풀기가 어려우면 NP-완전 문제일 수 있습니다
• 만약 문제에 집합 ( 라디오 기지국 집합처럼 ) 이 있고 풀기가 어려우면 NP-완전 문제일 수 있습니다
• 문제를 집합 커버링 문제나 외판원 문제로 재정의할 수 있다면, 명백하게 NP-완전 문제입니다