아직도 헷갈리는 NP 와 NP-hard

cdpark 님이 정리해 놓은 글을 발췌합니다.

NP : 답을 알려 주면, 그 답이 맞는지를 주어진 시간안에 검산해 볼 수 있는 문제
NP-hard : 답을 알려 주더라도, 그 답이 맞는지를 주어진 시간안에 검산할 수 없는 문제 

 
TSP 문제를 다음과 같이 만들면, 이는 NP 입니다..

"50개의 도시를 1000km 이내로 다 돌 수 있느냐?"

만약 누군가가 "A-B-C-D.... 순서로 돌면 가능하다." 라고 알려 줬을 때, 짧은 시간안에 이를 확인해 볼 수 있습니다. 즉, 맞는 답을 알려 주면, 검산을 통한 확인이 가능하지요.


하지만, TSP 문제를 다음과 같이 만들면, 이는 NP-hard 가 됩니다..

"50개의 도시를 다 도는 가장 짧은 길은 몇 km 이냐?"

만약 누군가가 "A-B-C-D... 순서로 도는 975km 가 답이다" 라고 알려 준다고 해도, 이보다 더 짧은 길이 있는지 없는 지를 알 수가 없습니다. 즉, 답을 알아도 이 답이 정말 맞는지 검산하는 것은 불가능이지요..

- 이쁜왕자 -
- Valken the SEXy THief~~ ^_* -