| [ KAIST ] in KIDS 글 쓴 이(By): jeehk (me) 날 짜 (Date): 2003년 12월 27일 토요일 오후 01시 51분 54초 제 목(Title): Re: [q] TSP 문제 감사합니다. 조금만 더 가르쳐 주시면 더더더 감사하겠습니다 (요즘 이게 또 화제가 되어서리... 정말 잊을만 하면 꼭 다시 들리는군요 =_=;) 주어진 candidate path가 최단경로인지 아닌지 확인하는 문제(decision 문제라고 하나요?)하고, 그냥 처음부터 최단경로를 찾는 문제(optimization?) 하고, 둘 중에 어떤 TSP를 말씀하신 것인지요? 둘다 똑같이 NP-complete 인가요? 그리고, 제가 이해한 게 맞다면, 아래의 문장들이 다 참이어야 할 것 같은데, 혹시 틀린 생각이 있다면 찝어 주시면 정말 감사하겠습니다 (OX퀴즈같네요...) 1. NP-Hard 문제 중에는 NP class가 아닌 것도 있다. 2. NP-complete 문제는 NP-Hard에 속한다. 3. NP-complete 문제들 중 하나만 다항시간에 풀 수 있는 방법이 있다면, 모든 NP 문제가 다항시간 안에 풀린다. 4. NP 문제들 중에는 NP-complete도 아니고 P도 아닌(혹은 P라고 증명 되지 않은) 문제들도 있다. 5. 모든 NP 문제는, 주어진 solution candidate가 정답인지 아닌지를 다항 시간 안에 판정할 수 있다 (deterministic Turing Machine으로). 6. NP-complete 문제의 정답을 내려면, (아직까지는) 모든 가능한 solution 공간을 exhaustive하게 탐색할 수 밖에 없다. 아... 중간에 적절한 pruning을 할 수는 있겠지만요... 말로 어떻게 표현해야 될지 잘 모르겠네요 |