| [ KAIST ] in KIDS 글 쓴 이(By): euphony (euphony) 날 짜 (Date): 2003년 12월 27일 토요일 오후 12시 28분 51초 제 목(Title): Re: [q] TSP 문제 TSP문제는 NP Problem이 맞는데요. 문제 A가 NP-Hard라는 얘기는, 모든 NP 문제에서 A로 Polynomial Reduction이 존재한다는 말로 알고 있습니다. 좀더 쉽게 말해보면, A를 푸는 Polynomial Algorithm이 존재하면, 모든 NP 문제를 푸는 Polynomial Algorithm을 얻을 수 있다는 것을 얘기하고 있습니다. A가 NP-Hard이면서 동시에 NP class에 들어가면, NP-complete이라고 합니다. TSP 문제의 경우는 NP Problem 이기도 하고, NP-Hard 이기도 하고, NP-Complete이기도 합니다. 하지만, NP-Complete이라고 하는게 가장 많은 정보를 주는게 되겠죠. 전산과 논문에서 NP-Hard라는 말을 종종 씁니다. "문제 A가 NP-Hard다. 즉 Polynomial time algorithm을 찾기가 무지하게 어렵다. 그러니까 빠르지만, 문제 A를 '대충' 푸는 알고리즘을 만들겠다." 이런식으로요. |