| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2002년 10월 24일 목요일 오후 01시 13분 29초 제 목(Title): P/NP/NP-complete/NP-hard 써 놓은게 아까와서.. QuizWit의 FAQ인 줄 알았는데 찾아보니 별로 없군요. 이상한 제목 속에 묻혀있나보네요. ------------------------------------------------------------------------- 대충 이렇게 생각하면 크게 틀리지 않습니다. P class: 시험 시간 안에 풀 수 있는 문제 NP class: (시험 시간 안에 풀 수 있는지는 모르겠지만), 답을 알려주면 맞는지 시간 안에 검산해볼 수 있는 문제 co-NP class: (시험 시간 안에 풀 수 있는지는 모르겠지만), 답을 알려주면 그 답이 틀렸는지 시간 안에 검산해 볼 수 있는 문제. P에 속하면 당연히 NP에 속합니다. (왜나면 직접 풀어서 알려준 답과 맞는지 비교하는 것도 검산의 한 방법이니..) 하지만 NP가 P인지는 모릅니다. (검산할 수 있다는 것과 풀 수 있다는 것의 차이...) ------------------------------------------------------------------------- NP-complete 는 그 중에서 한 문제만 P라고 풀려도 줄줄이 사탕으로 모든 NP 문제가 P로 풀린다는게 증명된 문제들입니다. 당연히 제일(!) 어려운 문제죠. 소수 판정은 NP-complete인지, P인지 다들 모르고 있었지만 다들 어려워하던 문제입니다. 그런데 P에 속한다는 증명이 나온 거죠. NP-complete가 P에 속한다면, 모든 NP 문제가 P에 속하게 되므로 소수 판정이 P라는 논문은 역사속으로 사라집니다. 하지만 NP 중의 하나라도 P가 아니라고 증명된다면... 꽤 복잡해집니다. P와 NP의 두 그룹으로 나뉘는게 아니라 그 사이에 자잘한 부류로 나뉩니다. (조금 어려운 문제, 많이 어려운 문제, 식으로요.) NP-hard는... NP class에 속하는지 증명되지는 않았지만, 이 문제가 풀리면 모든 NP 문제가 P에 풀린다고 증명되는 문제의 집합입니다. 즉, 시험 시간 안에 검산할 수는 없지만, 누군가가 맞는 공식을 알려주면 그걸 이용해서 다른 어려운 문제를 풀 수 있는 경우라고나 할까? 50개의 도시를 도는 TSP의 경우 NP-complete는.. "50개의 도시를 1000km 안에 다 돌 수 있느냐?"란 문제겠죠. 누군가가 "A-B-C-D 순으로 돌면 돼"라고 알려주면 그게 맞는지 검산해 볼 수 있습니다. NP-hard는.. "50개의 도시를 다 도는 가장 짧은 길은 몇 km냐?"죠. 누군가가 "A-B-C-D 순으로 돌면 975 km면 돼"라고 알려준다고 해도 혹시 "B-A-C-D" 순으로 도는게 더 짧을 수도 있으니 검산으로 확인해 볼 수 없죠. NP-hard 문제인 위 문제를 어떻게든 풀 수 있다면, 위의 NP-complete 버젼은 간단히 풀리겠죠? -- 박.. |