| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Banner) 날 짜 (Date): 1999년 2월 2일 화요일 오후 07시 08분 32초 제 목(Title): Re: [which re?] 공만들기 NP-complete에 관한 대답입니다. Decision problem들만을 다루는 것은 일반적인 문제들을 다루었을때 비직관적인 일들이 생기기 때문이고 NP-complete의 개념을 이해하기 위해서는 decision problem이냐 일반적인 문제이냐 등은 사실 생각 안해도 별 상관이 없습니다. (일반적인 문제들에 관해서는 FP, FNP, FNP-Complete 같은 class들이 있습니다.) 일반적인 문제로 봤을때 생기는 이상한 점은 다음과 같은 예에서 볼수 있습니다. 문제: 노드 n개를 가진 완전 그래프(모든 노드 사이에 에지가 있음)와 그 안의 두 노드를 주었을때 두 노드 사이의 길이가 n이하인 path를 모두 출력하라. 문제': 앞의 문제와 같은 상황에서 길이가 n이하인 path가 있는가? 처음 문제는 함수문제 (답을 요구)이구요 두번째 문제는 같은 문제의 decision version이지요. 직관적으로 두 문제는 "아주 쉬운"문제 입니다. 두번째 문제의 답은 항상 yes니까요. 그러면, 첫번째는? 쉽습니다. 하지만 답의 길이가 문제에 exponential하지요. 따라서 첫번째 문제는 polynomial time에 풀리지 않습니다. NP, P 같은 class들이 문제의 난이도를 구별하기 위해서 만든 것인데 일반적인 문제에서는 "난이도"라는 말이 좀 혼돈을 줄수도 있어서 decision problem들 만을 다루는 것으로 줄인 것입니다. 물론, 두가지 경우가 비슷해지는 것이 더 많구요. 따로따로 연구하기도 재미있는 분야 입니다. |