NP난해 (2) 썸네일형 리스트형 NP-완전 이해하기 (NP-Completeness) 지난번에 이어 이번에도 컴퓨터 과학의 최대 난제인 P vs NP에 대해서 좀더 깊게 들어가 보겠습니다. 이전 포스트에서는 P와 NP가 각각 직관적으로 어떤 의미를 갖고 있는지에 대해서 알아 보았는데요. 이를 보다 엄밀히 정의하면 다음과 같습니다. P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) \(X\)에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 \(X \in \mathrm{P}\)입니다. NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의.. 슈타이너 트리 2-근사 알고리즘 (2-Approximation for Steiner Tree) 코스워크가 모두 끝난 요즘 과거에 제대로 이해하지 못했거나 미처 보지 못하고 넘어간 것들을 제대로 공부해 보고자 교과서를 처음부터 다시 보고 있습니다. 공부하는 중에 개인적으로 정리도 할 겸 공유할 만한 내용이 있으면 포스팅을 하고자 합니다. 이번에 다룰 문제는 슈타이너 트리 문제(Steiner tree problem)입니다. 이 문제는 잘 알려진 최소 스패닝 트리 문제(minimum spanning tree problem, MST)의 일반화된 문제입니다. MST는 크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm) 등을 활용하여 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. 하지만 슈타이너 트리 문제는 NP-난해(NP-hard)하다고 알려.. 이전 1 다음
