| [ KAIST ] in KIDS 글 쓴 이(By): euphony (euphony) 날 짜 (Date): 2003년 12월 27일 토요일 오후 05시 35분 00초 제 목(Title): Re: [q] TSP 문제 제가 TSP 문제를 제대로 정의하지 않았네요. 제가 생각한 TSP 문제는, 주어진 m에 대해서 m이하의 cost가 드는 path가 존재하는가라는 문제입니다. 이 문제에 대한 NP algorithm은 Nondeterminism을 이용해서 만들 수 있습니다. nondeterminism은 컴퓨터를 여러개 동시에 돌린다고 보시면 되겠네요. Nondeterminism을 이용해서 특정 path를 컴색할 컴퓨터를 만들어냅니다. 만약 n개의 도시가 있다면, pick n1 from {1,2,..,n} : n개의 컴퓨터가 생깁니다 pick n2 from {1,2,..,n}-{n1} : nx(n-1)개의 컴퓨터가 생깁니다 ... pick nn from {1,2,..,n}-{n1,n2,..n(n-1)} : n!개의 컴퓨터가 있습니다. 라는 식으로 해서 path n1n2n3..nn를 검색할 컴퓨터를 만듭니다. 그리고 각 컴퓨터로 자신에게 주어진 path의 cost가 m이하인지 check하고 그러면 yes라고 대답합니다. 마지막으로 n!의 컴퓨터 중에 하나라도 yes라고 하면 사용자에게 yes라도 대답하고, 모두 그런 대답을 하지 않으면 no라도 대답합니다. 보시다싶이, 컴퓨터를 여러개 만들어 돌린다음, 그 중에 하나라도 yes라고 하는 것이 있으면 yes, 모두 yes라고 안하면 no라고 대답하는 알고리즘이 NP 알고리즘 입니다. (참고로 모두 yes라고 할때 yes, 아니면 no라도 대답하는 알고리즘은 co-NP 알고리즘이라고 합니다. 대강, NP는 "exists"와 관련있고, co-NP는 "for all"과 관련있습니다. NP와 co-NP가 일치하는가도 유명한 풀리지 않은 문제입니다.) 물어보신 것에 대한 대답으로 1. 그런 것 같은데요. 무식한 예제는 Halting problem이 될 수도 있겠네요. 2. 예 3. 예 4. 모르겠습니다. 만약 어떤 문제가 NP인데 NP-Complete은 아니고 P도 아니라는 것을 증명한다면, NP!=P가 증명됩니다. 그러니까 아직 사람들이 대답을 모를것이라 생각합니다. 5. 아마도 모든 NP 알고리즘에서 nondeterminstic choice를 앞으로 옮길 수 있는지, 그래서 NP algorithm 은 항상 nondeterministic choice를 먼저하고 deterministic turing machine으로 polynomial time에 check하는 형태로 쓰일 수 있는지 물으시는 것 같네요. 모르겠습니다. 컴플레서티이론 전공하시는 분이 아마 도와주셔야 겠네요. 6. 이것도 제 전공이 아니라 잘 모르겠네요. 주어들은 풍얼만 얘기하겠습니다. Exhaustive search를 하거나, 아니면 문제를 "최고로 좋은 값"이 아니라 "적당히 좋은 값"을 구하는 것으로 바꾸는 방법이 있다고 들었습니다. 책중에 이런 주제만을 다룬 것도 있다고 들었습니다. 컴플레서티 이론에는 "한 큐에" 유명해질 수 있는 많은 문제들이 있다고 들었습니다. 예를 들어서 1. 어떤 문제에 Randomized Polynomial Algorithm이 존재하면, Polynomial Algorithm이 존재하는가? 2. P=NP? 3. NP=co-NP? 등등등 1번 문제에 대해서는 많은 진전이 있었다고 얼핏들었는데, 역시 제 전공이 아니라서 확실히 설명을 못 드리겠네요. |