NP-Hard / NP-Compelete 의 개념

P와 NP의 개념을 알면 비교적 NP-Hard와 NP-Compelete를 이해하는 것은 쉬운 편입니다.

우선 NP-Haed의 개념부터 알아보겠습니다. 

 

 

NP-Hard

---

NP-Hard: NP 클래스 안에 있는 모든 문제가 어떤 문제 Q로 Reducible하면, 그 문제 Q는 NP-Hard이다. 

위의 정의를 완벽히 이해하기 위해 우선 Redicule의 뜻을 함께 이해해보겠습니다.

P와 Q라는 문제가 있다고 해보겠습니다. 그런데 Q를 풀 수있는 알고리즘으로 P를 풀어냈습니다. 그렇다면 문제Q가 P보다 어렵거나 같은 수준의 문제라고 할 수 있습니다. 이런 상황을 Problem P is reducible to Q(to 뒤에 있는게 더 어렵거나 같다)라고 표현합니다!! 여기서 짚고 넘어갈 점은 P를 Q를 풀 수있는 알고리즘으로 풀었다고 해서 Q가 무조건 P보다 어렵다가 아니라 같은경우도 포함한다는 것입니다. 

 

야구로 예시를 들어보겠습니다. 타자는  투수가 시속 150km의 이상의 공을 던지면 안타를 치지 못한다고 생각해 보겠습니다. 그렇다면 150km보다 빠르게 155km, 160km를 던지는 투수들은 당연히 타자가 공을 치지 못하게 할 수 있습니다. 그리고 150km를 던지는 A,B 두 투수가 던져도 타자는 안타를 치지 못합니다. A와 B선수는 서로 던질 수 있는 공의 속도가 같고, '타자가 안타를 치지 못하게 해야한다'라는 문제를 해결할 수 있습니다. A와 B선수는 서로 reducible된다고 생각할 수 있겠네요! 예시가 도움이 되셨을지 모르겠네요 ...... 

 

그리고 Q를 풀 수 있는 알고리즘으로 NP클래스 안에 있는 모든 문제를 풀 수 있다면, Q를 NP-Hard라고 합니다. NP-Hard의 경우 Reducible의 개념만 정확하게 알면 이해하는데 큰 어려움은 없을것 같습니다!

 

 

 

 

NP-Complete

---

NP-Complete: NP-Hard이면서 NP클래스에 있는 문제이다.

위의 정의가 NP-Complete의 정의입니다. 지금까지 NP클래스와 NP-Hard에 대해 이해하셨다면 이해하는데 어렵지 않을거라는 생각이 듭니다. 

조금이라도 풀어서 다시 정리하면, 'NP클래스에 속해 있으면서 어떤 기준에 의해 가장 어려운 문제'라고 할 수 있습니다.

 

 

마지막으로 지금까지 공부한 클래스P, 클래스NP, NP-Hard, NP-Complete의 관계를 나타내는 그래프프입니다. 

 

현재까지는 왼쪽 그림과 같이 관계를 표현할 수 있습니다. 이미 클래스P가 클래스NP에 속한다는 것이 증명되었습니다. 

만약 클래스NP가 클래스P에 속한다는 것이 증명된다면 P=NP가 될것이고 오른쪽 그림처럼 관계를 표현할 수 있습니다. 

많은 학자들이 P=NP라는 것을 증명하기 위해 도전하였지만, 누구도 증명하지 못했습니다.