다항 시간 근사 해법

다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다.

PTAS는 어떤 주어진 상수 ${\displaystyle \epsilon >0}$에 대해서, 최적해로부터 ${\displaystyle \epsilon }$배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가 ${\displaystyle (1+\epsilon )L}$을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.)

EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 ${\displaystyle f(\epsilon )g(n)}$ 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 ${\displaystyle \epsilon }$에 독립적인 ${\displaystyle O(n^{c})}$의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, ${\displaystyle O(e^{1/\epsilon }n^{2})}$는 EPTAS이다.

FPTAS(fully polynomial-time approximation scheme)는 EPTAS보다 더 강한 조건으로, PTAS 알고리즘 중에서 시간 복잡도가 ${\displaystyle 1/\epsilon }$에 대해서 다항 시간을 만족해야 한다. 예를 들어, ${\displaystyle O((1/\epsilon )^{2}n^{2})}$는 FPTAS를 만족하며, ${\displaystyle \Theta (n^{1/\epsilon })}$는 PTAS이지만 FPTAS는 아니다.

• 복잡도 동물원: PTAS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems - PTAS가 있는 NP 최적화 문제 목록