В теории сложности вычислений класс 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.
Другие проблемы, связанные с APX, включают в себя:
PTAS ( схема аппроксимации полиномиального времени ) состоит из задач, которые можно аппроксимировать с точностью до любого постоянного коэффициента, кроме 1, за время, полиномиальное по отношению к размеру входных данных, но полином зависит от такого фактора. Этот класс является подмножеством APX.
Если P = NP , в APX существуют проблемы, которые не являются ни PTAS, ни APX-полными. Такие задачи можно рассматривать как имеющие сложность между задачами PTAS и APX-полными задачами, и их можно назвать APX-промежуточными . Считается, что проблема упаковки контейнеров является промежуточной по APX . Несмотря на отсутствие известного PTAS, задача упаковки контейнеров имеет несколько «асимптотических PTAS» алгоритмов, которые ведут себя как PTAS, когда оптимальное решение велико, поэтому интуитивно это может быть проще, чем задачи, которые являются APX-сложными.
Еще один пример потенциально промежуточной проблемы APX — минимальная раскраска ребер .
Можно также определить семейство классов сложности -APX, где -APX содержит задачи с алгоритмом аппроксимации полиномиального времени с коэффициентом аппроксимации. Аналогично можно определить -APX-полные классы; некоторые такие классы содержат хорошо известные задачи оптимизации. Лог-APX-полнота и поли-APX-полнота определяются с точки зрения AP-сокращения, а не PTAS-сокращения; это связано с тем, что PTAS-сокращения недостаточно сильны, чтобы сохранить членство в Log-APX и Poly-APX, хотя для APX их достаточно.
Log-APX-complete, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до логарифмического фактора входного размера, включает минимальный доминирующий набор , когда степень не ограничена.
Поли-APX-полный, состоящий из сложнейших задач, которые можно эффективно аппроксимировать с точностью до факторного полинома от входного размера, в общем случае включает максимальное независимое множество .
Также существуют задачи, которые являются exp-APX-полными, где коэффициент аппроксимации экспоненциально зависит от входного размера. Это может произойти, когда аппроксимация зависит от значения чисел в экземпляре задачи; эти числа могут быть выражены в логарифмическом пространстве по их значению, отсюда и экспоненциальный множитель.
