中庸 中庸

어떤 Algorithm 이 polynomial - time 에 동작하는 경우 즉, O(n^d) 에 동작하는 경우에 해당 알고리즘을 보통 Effecient Algorithm 이라고 합니다. 보통의 경우, 어떤 문제를 해결하는 Efficient Algorithm 을 찾기 위해서는 그 문제를 polynomial time 에 동작하는 reduction 이 가능한지를 생각하며, 이를 polynomial-time reduction 이라고 합니다. Polynomial Time Reduction 의 정의를 살펴보겠습니다. Definition of Polynomial Time Reduction Decision Problem X 에서 Decision Problem Y 로의 Polynomial Time Reduction 은..