다항 시간 근사 해법

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

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

EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가  꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 에 독립적인 의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, 는 EPTAS이다.

FPTAS(fully polynomial-time approximation scheme)는 EPTAS보다 더 강한 조건으로, PTAS 알고리즘 중에서 시간 복잡도가 에 대해서 다항 시간을 만족해야 한다. 예를 들어, 는 FPTAS를 만족하며, 는 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 최적화 문제 목록

근사 알고리즘