Введение
Класс сложности приближённых задач
В теории вычислительной сложности класс APX (сокращение от "приблизимый") — это множество задач оптимизации NP, для которых существуют полиномиальные алгоритмы приближения с коэффициентом приближения, ограниченным константой (или, кратко, алгоритмы приближения с постоянным фактором). Проще говоря, для задач этого класса существуют эффективные алгоритмы, способные находить решение, отличающееся от оптимального не более чем на фиксированный множитель. Алгоритм называется алгоритмом приближения для входного размера , если можно доказать, что найденное им решение не более чем в раз хуже оптимального. Здесь коэффициент называется коэффициентом приближения. Задачи в APX — это задачи, для которых коэффициент приближения является константой. Коэффициент приближения обычно указывается больше 1. В случае задач минимизации значение, найденное алгоритмом, делится на оптимальное значение, а для задач максимизации – наоборот. Для задач максимизации, где худшее решение имеет меньшее значение, коэффициент приближения иногда указывается меньше 1; в таких случаях обратная величина коэффициента является отношением значения найденного решения к оптимальному значению. Задача обладает полиномиальной схемой приближения по времени (PTAS), если для любого множителя, на который найденное решение может быть хуже оптимального (меньше 1), существует полиномиальный по времени алгоритм для решения задачи с такой точностью. Если P ≠ NP, существуют задачи, принадлежащие APX, но не имеющие PTAS, следовательно, класс задач с PTAS строго содержится в APX. Одной из таких задач является задача упаковки в контейнеры.
Твердость и полнота APX
Проблема считается APX-трудной, если существует PTAS-сокращение из каждой задачи из APX к этой задаче, и APX-полной, если задача APX-трудная и также принадлежит классу APX. Как следствие из P ≠ NP ⇒ PTAS ≠ APX, если предположить, что P ≠ NP, ни одна APX-трудная задача не имеет PTAS-схемы. На практике, для доказательства APX-полноты одной задачи, её часто сводят к другой, используя альтернативные схемы сокращений, такие как L-сокращения, которые подразумевают PTAS-сокращения.
ПТАС
PTAS (полиномиальная схема аппроксимации) — это класс задач, которые могут быть аппроксимированы с точностью до любого постоянного коэффициента, отличного от 1, за время, полиномиальное от размера входных данных, однако степень полинома зависит от этого коэффициента. Этот класс является подмножеством APX.
APX-посредник
Если P не равно NP, в классе APX существуют задачи, которые не принадлежат ни PTAS, ни классу APX-полных задач. Такие задачи можно рассматривать как обладающие сложностью, промежуточной между задачами PTAS и APX-полными задачами, и их можно назвать APX-промежуточными. Считается, что задача о размещении предметов в контейнерах является APX-промежуточной. Несмотря на отсутствие известного PTAS, для задачи о размещении предметов в контейнерах существует несколько "асимптотических PTAS", которые ведут себя как PTAS при больших оптимальных решениях, поэтому интуитивно она может быть проще, чем APX-трудные задачи. Другим примером потенциальной APX-промежуточной задачи является задача минимальной окраски рёбер.
f ((n) -APX
Можно также определить семейство классов сложности APX, где APX содержит задачи, для которых существует алгоритм приближения в полиномиальное время с коэффициентом приближения. Аналогично можно определить APX-полные классы; некоторые из этих классов содержат хорошо известные задачи оптимизации. Log APX-полнота и Poly APX-полнота определяются с помощью AP-сводимостей, а не PTAS-сводимостей; это связано с тем, что PTAS-сводимостей недостаточно для сохранения принадлежности к Log APX и Poly APX, хотя они достаточны для APX. Log APX-полный класс состоит из самых сложных задач, которые можно эффективно приближать с точностью до фактора, логарифмически зависящего от размера входных данных, и включает в себя задачу о минимальном доминирующем множестве при неограниченной степени вершин. Poly APX-полный класс состоит из самых сложных задач, которые можно эффективно приближать с точностью до фактора, полиномиально зависящего от размера входных данных, и включает в себя задачу о максимальном независимом множестве в общем случае. Существуют также задачи, являющиеся exp APX-полными, где коэффициент приближения экспоненциально зависит от размера входных данных. Это может происходить, когда приближение зависит от значений чисел в экземпляре задачи; эти числа могут быть представлены в пространстве, логарифмически зависящем от их значения, что и приводит к экспоненциальному фактору.