저번 포스팅에서는 P와 NP에 대해서 알아보았다.
어려운 내용이지만, 이어서 NP-Hard와 NP-complete에 대해서 알아보겠다.
NP-hard???
먼저, NP-hard의 이론적인 정의는 다음과 같다.
NP에 속하는 모든 문제 L에 대해서 어떤 결정문제 H로 다대일 환원(reduction)할 수 있다면, 문제 H는 NP-hard이다.
(A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H)
문제가 환원된다..??
reduction은 어떤 문제를 다른 문제로 변환(transform)하는 알고리즘을 말한다.
보통, 문제 A가 문제 B로 환원되는 것을 보임으로서 문제 B가 적어도 문제 A보다 어렵거나 똑같이 어렵다는 것을 보이기 위해 사용된다.
즉, 문제 B를 효율적으로 풀 수 있는 알고리즘이 문제 A를 푸는 데 쓰일 수 있다면(subroutine) 문제 A가 문제 B로 환원될 수 있는 것이다.
환원에 대한 간단한 예를 들어보자.
5*8이라는 곱셈문제가 있다. 이는 5+5+5+5+5+5+5+5와 같다.
이처럼, 덧셈 문제로 곱셈 문제를 표현할 수 있고, 이 말은 덧셈(문제 B)이 곱셈(문제 A)를 푸는 데 쓰일 수 있다는 것이다.
즉, 곱셈(문제 A)는 덧셈(문제 B)으로 환원될 수 있는 것이다.
결국 덧셈은 적어도 곱셈보다는 어렵거나 똑같이 어려운 문제인 것이다.
여기서 ‘어렵다’는 건 시간이나 공간과 같은 계산 자원(computational resource)이 더 많이 필요하다는 것이다.
실제로 위 예시에서, 곱셈은 한번의 계산이면 되지만, 덧셈은 8번의 계산이 필요하다.
다시, NP-hard로 돌아와서..
NP-hard는 NP의 모든 문제를 환원할 수 있는 문제랬다.
다시 말하면, NP-hard는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합인 것이다.
그럼 NP-complete는??
NP-hard까지 왔다면, NP-complete는 그나마 심플하다.
NP-complete의 정의는 다음과 같다.
NP-hard이면서 NP이면 NP-complete이다.
즉, 풀 수 있는 문제들 중에서 가장 어려운 문제다.
다음은 대표적인 NP-complete문제인데, TSP문제도 포함된다!
드디어 조금은 이해했다..!
마지막으로, 앞서 설명한 모든 내용들의 관계를 잘 나타내는 다이어그램이다.
아직은 P=NP임이 증명되지 않았기 때문에 두가지 경우를 나눠서 구분해준다.
많은 분들이 블로그에 설명을 잘해두셔서 미숙하게나마 NP-hard에 대해 정리할 수 있었습니다…
틀린 부분도 분명 있을 것 같습니다. 언제든 피드백 주시면 감사히 배우겠습니다.
다음에는 NP-complete에 해당하는 SAT문제나 TSP문제 등에 대해서도 다뤄보고자 합니다.