Класс APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач , для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры , который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число.

Аппроксимационный алгоритм называется алгоритмом c -аппроксимации с некоторой константой c , если можно доказать, что решение, полученное с помощью этого алгоритма, хуже оптимального не более чем в c раз .

Константа c называется коэффициентом аппроксимации . В зависимости от того, является ли проблема проблемой максимизации или минимизации, решение может быть в c раз больше или в c раз меньше оптимального.

К примеру, и задача о вершинном покрытии , и задача коммивояжёра с неравенством треугольника имеют простые алгоритмы, для которых c = 2 . С другой стороны, доказано, что задачу коммивояжёра с произвольными длинами рёбер (не обязательно удовлетворяющими неравенству треугольника) нельзя аппроксимировать с постоянным коэффициентом, поскольку задачу поиска гамильтонова пути нельзя решить за полиномиальное время (в случае, если P ≠ NP ) .

Если существует алгоритм решения задачи за полиномиальное время для любого фиксированного коэффициента большего единицы (один алгоритм для любого коэффициента), говорят, что задача имеет полиномиальную по времени схему аппроксимации ( PTAS ) . Если P ≠ NP, можно показать, что существуют задачи, входящие в класс APX , но не в PTAS , то есть задачи, которые можно аппроксимировать с некоторым коэффициентом, но не с любым коэффициентом.

Задача называется APX -трудной, если любая задача из класса APX имеет сведение к этой задаче, и APX -полной, если задача APX -трудна и сама принадлежит к классу APX . Из неравенства P ≠ NP следует, что PTAS ≠ APX , P ≠ NP, а отсюда никакая APX -трудная задача не принадлежит PTAS .

Если задача APX -трудна, это обычно плохо, поскольку при P ≠ NP это означает отсутствие PTAS -алгоритма, который является наиболее полезным видом аппроксимационного алгоритма. Одна из наиболее простых APX -полных задач — это , вариант задачи выполнимости булевых формул . В этой задаче мы имеем булеву формулу в конъюнктивной нормальной форме , и хотим получить максимальное число подвыражений, которые будут выполняться при единственной подстановке значений true/false в переменные. Несмотря на то, что, скорее всего, задача не принадлежит PTAS , верное значение может быть получено с точностью 30 %, а некоторые упрощённые варианты задачи имеют PTAS .

Примеры

• Алгоритм Кристофидеса

Примечания

Ссылки

• C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. от 13 апреля 2007 на Wayback Machine . от 5 апреля 2007 на Wayback Machine . Last updated March 20, 2000.