Введение
Полностью полиномиальная схема временного приближения (FPTAS) — это алгоритм для нахождения приближенных решений функциональных задач, особенно задач оптимизации. FPTAS принимает на вход экземпляр задачи и параметр ε > 0. Он возвращает в качестве результата значение, которое не менее (1-ε) раз больше правильного значения, и не более (1+ε) раз больше правильного значения. В контексте задач оптимизации под правильным значением понимается значение оптимального решения, и часто подразумевается, что FPTAS должен выдавать допустимое решение (а не только значение решения). Возврат значения и нахождение решения с этим значением эквивалентны, если задача обладает саморедукцией. Важно отметить, что время работы FPTAS является полиномиальным по размеру задачи и по 1/ε. Это отличается от общей полиномиальной схемы временного приближения (PTAS). Время работы общей PTAS является полиномиальным по размеру задачи для каждого конкретного ε, но может быть экспоненциальным по 1/ε. Термин FPTAS также может использоваться для обозначения класса задач, для которых существует FPTAS. FPTAS является подмножеством PTAS, и, если P ≠ NP, то это строгое подмножество.
Отношение к другим классам сложности
Все задачи в FPTAS разрешимы за время, зависящее от фиксированного параметра, относительно стандартной параметризации. Любая строго NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS, если P=NP. Однако обратное неверно: например, если P не равно NP, задача о рюкзаке с двумя ограничениями не является строго NP-трудной, но не имеет FPTAS даже при полиномиальной ограниченности оптимальной целевой функции.
Преобразование динамической программы в FPTAS
Вёгингер представил общую схему преобразования определённого класса динамических программ в FPTAS.
Непримеры
Несмотря на общую применимость вышеуказанного результата, существуют случаи, когда его нельзя использовать. 1. В задаче о суммарной задержке 1||, формулировка динамического программирования Лоулера требует обновления всех состояний в старом пространстве состояний порядка B раз, где B сопоставимо с X (максимальным размером входных данных). То же справедливо и для динамического программирования при определении оптимального размера экономической партии. В этих случаях число переходных функций в F равно B, что является экспоненциальным от log(X), и, следовательно, нарушается второе техническое условие. Метод обрезки состояний неэффективен, но для разработки FPTAS был использован другой метод – округление входных данных. 2. В задаче минимизации дисперсии 1||, целевая функция имеет вид , что нарушает условие 2, и, следовательно, теорему нельзя применить. Однако для разработки FPTAS использовались другие методы.
FPTAS для приближения реальных чисел
Другой тип задач, в которых FPTAS может быть полезен, — это нахождение рациональных чисел, аппроксимирующих некоторые действительные числа. Например, рассмотрим бесконечный ряд. Сумма является иррациональным числом. Чтобы аппроксимировать его рациональным числом, мы можем вычислить сумму первых k элементов, для некоторого конечного k. Можно показать, что погрешность аппроксимации составляет примерно. Следовательно, чтобы получить погрешность ε, нам потребуется около элементов, что делает этот алгоритм FPTAS. Обратите внимание, что эта конкретная сумма может быть представлена другим способом, в котором требуется только O(log(ε)) элементов, поэтому сумма может быть фактически аппроксимирована за полиномиальное время относительно длины кодирования ε.