примерный
В теории вычислительной сложности класс APX (аббревиатура от «аппроксимируемый») представляет собой набор задач оптимизации NP , которые позволяют использовать алгоритмы аппроксимации с полиномиальным временем с коэффициентом аппроксимации, ограниченным константой (или алгоритмами аппроксимации с постоянным коэффициентом для краткости). Проще говоря, задачи этого класса имеют эффективные алгоритмы , которые могут найти ответ в пределах некоторого фиксированного мультипликативного коэффициента оптимального ответа.
Алгоритм аппроксимации называется -алгоритмом аппроксимации размера входных данных , если можно доказать, что решение, которое находит алгоритм, не более чем в несколько раз хуже, чем оптимальное решение. Здесь называется коэффициентом аппроксимации . Проблемы в APX связаны с алгоритмами, для которых коэффициент аппроксимации является постоянным . Коэффициент аппроксимации обычно указывается больше 1. В случае задач минимизации оценка найденного решения делится на оценку оптимального решения, а для задач максимизации - наоборот. Для задач максимизации, где худшее решение имеет меньшую оценку,иногда указывается меньше 1; в таких случаях обратным является отношение оценки найденного решения к оценке оптимального решения.
Говорят, что задача имеет схему аппроксимации с полиномиальным временем ( PTAS ) , если для каждого мультипликативного фактора оптимума, худшего, чем 1, существует алгоритм с полиномиальным временем для решения проблемы с точностью до этого фактора. Если P = NP , то существуют задачи, находящиеся в APX, но без PTAS, поэтому класс задач с PTAS строго содержится в APX. Одной из таких проблем является проблема упаковки в корзину .
Говорят, что проблема является APX-сложной , если существует сокращение PTAS от каждой проблемы в APX к этой проблеме, и APX-полной , если проблема APX-сложная, а также в APX. Как следствие P ≠ NP ⇒ PTAS ≠ APX, если предполагается P ≠ NP, ни одна APX-сложная задача не имеет PTAS. На практике сведение одной задачи к другой для демонстрации APX-полноты часто выполняется с использованием других схем редукции, таких как L-редукции , подразумевающие PTAS-редукции.
Одной из самых простых APX-полных задач является MAX-3SAT-3 , разновидность булевой задачи выполнимости . В этой задаче у нас есть логическая формула в конъюнктивной нормальной форме , в которой каждая переменная встречается не более 3 раз, и мы хотим знать максимальное количество предложений, которые могут быть одновременно удовлетворены одним присвоением значений true/false переменным.
PTAS ( схема аппроксимации полиномиального времени ) состоит из задач, которые могут быть аппроксимированы с точностью до любого постоянного коэффициента, кроме 1, за время, которое полиномиально размеру входных данных, но полином зависит от такого коэффициента. Этот класс является подмножеством APX.