시간 복잡도1 P, NP, NP-Complete, NP-Hard, 시간 복잡도 # 아주 직관적인 설명P: 폴리노미얼 타임으로 완전한 정답을 구할 수 있는 쉬운 문제 NP: 임의의 값 하나에 대해서만 그것이 정답인지 아닌지 폴리노미얼 타임이하로 계산가능한 검산만 쉬운 문제보통 NP를 풀때는 휴리스틱 탐색 등의 계산적인 접근법을 사용한다. 위의 정의에서 P 문제는 애초에 폴리노미얼 타임으로 정답을 구할 수 있으므로, 당연 그 시간내에 검산도 가능하다. 따라서 P ⊂ NP이다. NP-Hard: NP-Hard는 계산복잡도가 NP일 수도 있고, 그보다 더 어려울 수도 있다. NP-Hard >= NP영어로는 이렇게 표현한다. "at least as hard as the hardest problems in NP". 그런데 여기서 어렵다의 의미가 조금 복잡하다. 어떤 NP문제를 다른 문제로 다항.. 2014. 7. 22. 이전 1 다음
