В информатике (в частности , в алгоритмике ) схема аппроксимации с полиномиальным временем ( PTAS ) — это тип алгоритма аппроксимации задач оптимизации ( чаще всего NP-трудных задач оптимизации).
PTAS — это алгоритм, который берет пример задачи оптимизации и параметр ε > 0 и выдает решение, которое находится в пределах коэффициента 1 + ε от оптимального (или 1 – ε для задач максимизации). Например, для евклидовой задачи коммивояжера PTAS создаст тур длиной не более (1 + ε) L , где L — длина самого короткого тура. [1]
Время работы PTAS должно быть полиномиальным по размеру задачи для каждого фиксированного ε, но может быть разным для разных ε. Таким образом, алгоритм, работающий за время O ( n 1/ε ) или даже O ( n exp(1/ε) ), считается PTAS.
Практическая проблема с алгоритмами PTAS заключается в том, что показатель полинома может резко увеличиваться при уменьшении ε, например, если время выполнения равно O ( n (1/ε)! ) . Один из способов решения этой проблемы — определить эффективную схему аппроксимации с полиномиальным временем или EPTAS , в которой время работы должно быть O ( nc ) для постоянной c , независимой от ε . Это гарантирует, что увеличение размера задачи будет иметь одинаковое относительное влияние на время выполнения независимо от того, какое ε используется; однако константа под большим О может по-прежнему зависеть от ε произвольно. Другими словами, EPTAS работает за время FPT , где параметром является ε.
Еще более ограничительной и полезной на практике является схема аппроксимации с полностью полиномиальным временем или FPTAS , которая требует, чтобы алгоритм был полиномиальным как по размеру задачи n , так и по 1/ε .
Если P = NP , то FPTAS ⊊ PTAS ⊊ APX . [2] Следовательно, при этом предположении APX-сложные задачи не имеют PTAS.
Другим детерминированным вариантом PTAS является схема аппроксимации квазиполиномиального времени или QPTAS . QPTAS имеет временную сложность n полилог ( n ) для каждого фиксированного ε > 0 . Кроме того, PTAS может работать за время FPT для некоторой параметризации задачи, что приводит к параметризованной схеме аппроксимации .
Некоторые задачи, не имеющие PTAS, могут допускать рандомизированный алгоритм с аналогичными свойствами, схему рандомизированной аппроксимации с полиномиальным временем или PRAS . PRAS — это алгоритм, который берет пример задачи оптимизации или подсчета и параметр ε > 0 и за полиномиальное время выдает решение, которое с высокой вероятностью находится в пределах коэффициента ε от оптимального. Обычно «высокая вероятность» означает вероятность более 3/4, хотя, как и в случае с большинством вероятностных классов сложности, это определение устойчиво к изменениям этого точного значения (минимальное требование обычно превышает 1/2). Как и PTAS, PRAS должен иметь полиномиальное время работы от n , но не обязательно от ε ; с дополнительными ограничениями на время работы в ε можно определить эффективную схему рандомизированной аппроксимации с полиномиальным временем или EPRAS , аналогичную EPTAS, и схему рандомизированной аппроксимации с полностью полиномиальным временем или FPRAS , аналогичную FPTAS. [3]
Термин PTAS также может использоваться для обозначения класса задач оптимизации, в которых есть PTAS. PTAS — это подмножество APX , и, если P = NP , это строгое подмножество. [2]
Членство в PTAS можно показать с помощью PTAS-редукции , L-редукции или P-редукции , все из которых сохраняют членство в PTAS, и их также можно использовать для демонстрации PTAS-полноты. С другой стороны, продемонстрировать непринадлежность к PTAS (а именно, отсутствие PTAS) можно, показав, что проблема является APX-сложной, после чего существование PTAS покажет P = NP. Твердость APX обычно проявляется через снижение PTAS или снижение AP .