Задача P называется в APX, если существует некоторая постоянная c> 0 такая, что для P существует алгоритм аппроксимации за полиномиальное время с коэффициентом аппроксимации 1 + c.
APX содержит PTAS (это можно увидеть, просто выбрав любую константу c> 0) и P.
APX в NP? В частности, означает ли существование алгоритма аппроксимации за полиномиальное время для некоторого фактора аппроксимации, что задача находится в NP?
Ответы:
APX определяется как подмножество NPO, так что да, если проблема оптимизации находится в APX, то соответствующая проблема решения находится в NP.
Однако, если вы спрашиваете, должна ли быть произвольная проблема в NP (или NPO), если есть O-1-аппроксимация по времени, то ответ - нет. Я не знаю каких-либо естественных проблем, которые служат контрпримером, но можно определить искусственную проблему максимизации, где целью является сумма двух слагаемых, большого слагаемого, который легко оптимизируется в P, и гораздо меньшего слагаемого. это добавляет небольшое количество, если часть решения кодирует ответ на какую-то сложную проблему (за пределами NP). Тогда вы можете найти, скажем, 2-аппроксимацию по времени, сконцентрировавшись на простом члене, но для поиска оптимального решения потребуется решение сложной задачи.
источник
APX обсуждается и (как и другие классы сложности) регулярно обновляется в зоопарке сложности.
http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#apx
источник