[Algorithms] NP 이론(NP theory)

알고리즘 수업을 들을때도 이 부분은 안드로메다였는데, 뭔가 알겠다 싶었는데 다시 보니까 더 헷갈린다. 그래도 안볼수는 없으니 이해하며 정리해보자. 일단 Decision problem의 정의에 대해서 알아야 한다. Decision Problem은 어떠한 인스턴스에 대해서 "yes" or "no"로 답할 수 있는 문제를 말한다. 쉬운 예를 들자면, 스무고개를 하면 질문을 할때 예 또는 아니오로만 답할 수 있는 질문을 해야한다. 그러한 문제들을 decision problem이라고 보면 되겠다. 이어서 집합 P와 NP의 정의는 다음과 같다. P : 다항식 시간(polynomial-time)의 알고리즘으로 풀리는 decision problem의 집합 NP : 비결정적 다항식시간(polynomial-time non..
Computer Science 2011. 7. 7. 11:41
1