Analysis of Algorithms | Pseudo-polynomial Algorithms

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

Pseudo-polynomial이란?

알고리즘의 복잡도를 산정할 시 최악의 경우에 대한 시간 복잡도가 input의 크기(size of bit)가 아닌 input의 값(size of value)으로 결정되는 알고리즘을 Pseudo-polynomial algorithm(의사-다항식 알고리즘) 이라 부른다.

예를 들어 임의로 정의한 자연수로 이루어진 배열 내에 존재하는 모든 값에 대한 빈도를 알고싶다고 하자. pseudo-polynomial 시간이 걸리는 해결방법은 최대값을 찾고 1부터 최대값까지 모든 경우의 수를 1개씩 찾는 것이다. 이 방법은 배열 내에 존재하는 최대값의 크기(size of value)가 얼마인지에 따라 해결시간이 결정되기 때문에 pseudo-polynomial의 성격을 갖는다. 그렇다면 반대로 시간복잡도의 크기가 input의 크기에만 의존하는 경우는 Polynomial algorithm이라고 부른다.

Pseudo-polynomial 과 NP-Completeness

뒤에서 다룰 NP관련 문제 중 NP-Complete(NP-완전) 문제 중엔 Pseudo Polynomial 시간을 요구하는 알고리즘을 해법으로 갖는다. 예를 들자면 Dynamic Programming으로 해결되는 0-1 Knapsack, Subset-Sum 문제를 들 수 있다. NP-Complete 문제 중 pseudo-polynomial 시간을 갖는 알고리즘으로 해결할 수 있는 문제를 weakly NP-Complete 문제라고 부른다.

참고자료

1. Pseudo-polynomial Algorithms