ComputerScience/Computational Complexity (1) 썸네일형 리스트형 NP complete 우선 NP complete를 이해하기 위해 필요한 용어들을 먼저 정의한다. Abstract problem $Q$란 instance set $I$ 와 solution set $S$사이의 binary relation 을 의한다. 예를 들어, 최단경로 문제의의 instance는 Graph와 두 개의 vertices 들로 이루어져 있을 수 있다. 여기서 우리는 solution이 yes or no 에 해당하는 Decision Problem에만 집중한다. Decision Problem의 예시는 다음과 같다. 최단경로 문제 중 k step 안에 vertex u에서 vertex v로 가는 경로가 존재하는지를 묻는 문제를 PATH라고 할 때, instance $i= $로 정의하며 , $PATH(i)=0 \; \text{.. 이전 1 다음