В информатике (в частности , в алгоритмике ) схема аппроксимации с полиномиальным временем ( 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 ( n c ) для константы c , независимой от ε . Это гарантирует, что увеличение размера задачи будет иметь одинаковый относительный эффект на время выполнения независимо от того, какое ε используется; однако константа под большим O все еще может произвольно зависеть от ε. Другими словами, EPTAS выполняется за время FPT , где параметром является ε.
Еще более ограничительной и полезной на практике является схема аппроксимации с полностью полиномиальным временем или FPTAS , которая требует, чтобы алгоритм был полиномиальным как по размеру задачи n , так и по 1/ε .
Если P = NP , то выполняется FPTAS ⊊ PTAS ⊊ APX . [2] Следовательно, при этом предположении APX-трудные проблемы не имеют PTAS.
Другим детерминированным вариантом PTAS является схема приближения квазиполиномиального времени или QPTAS . QPTAS имеет временную сложность n polylog ( 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-сокращения .