APX содержится в NP?

15

Задача P называется в APX, если существует некоторая постоянная c> 0 такая, что для P существует алгоритм аппроксимации за полиномиальное время с коэффициентом аппроксимации 1 + c.

APX содержит PTAS (это можно увидеть, просто выбрав любую константу c> 0) и P.

APX в NP? В частности, означает ли существование алгоритма аппроксимации за полиномиальное время для некоторого фактора аппроксимации, что задача находится в NP?

Эндрю В.
источник
Я думаю, что «то, что известно о классе X относительно всех других классов Y», является слишком неопределенным вопросом, если только не будет предоставлена ​​дополнительная информация о типах искомых отношений.
Андрас Саламон
Я имею в виду такие отношения, как «содержит», «содержится в», «не содержит».
Эндрю В.
Подумав немного, я сузил вопрос до конкретных отношений, которые меня больше всего интересуют.
Эндрю У.
1
Что именно значит спрашивать, содержится ли APX в NP? APX состоит из приближенных задач «NP-оптимизации», тогда как NP состоит из задач решения. Кроме того, по определению, вариант решения проблемы NP-оптимизации находится в NP. Может быть, вы имели в виду что-то еще?
Джошуа Грохов
Вы правы, Джошуа. Ян ответил на вопрос, который я должен был задать.
Эндрю В.

Ответы:

20

APX определяется как подмножество NPO, так что да, если проблема оптимизации находится в APX, то соответствующая проблема решения находится в NP.

Однако, если вы спрашиваете, должна ли быть произвольная проблема в NP (или NPO), если есть O-1-аппроксимация по времени, то ответ - нет. Я не знаю каких-либо естественных проблем, которые служат контрпримером, но можно определить искусственную проблему максимизации, где целью является сумма двух слагаемых, большого слагаемого, который легко оптимизируется в P, и гораздо меньшего слагаемого. это добавляет небольшое количество, если часть решения кодирует ответ на какую-то сложную проблему (за пределами NP). Тогда вы можете найти, скажем, 2-аппроксимацию по времени, сконцентрировавшись на простом члене, но для поиска оптимального решения потребуется решение сложной задачи.

Ян
источник
2
Я принял ваш ответ, потому что он касался как вопроса, который я задал («Содержится ли APX в NP?»), Так и вопроса, который я должен был задать («Означает ли поли-время O (1) точное решение в NP?»).
Эндрю В.
1
Класс проблем онлайн, который не содержится в NPO и NP, но имеет постоянное приближение, является классом онлайн-задач (вопрос о том, какой класс сложности содержит онлайн-задачи, находится здесь cstheory.stackexchange.com/questions/1664/… ) ,
Александр Бондаренко
8

APX обсуждается и (как и другие классы сложности) регулярно обновляется в зоопарке сложности.

http://qwiki.stanford.edu/wiki/Complexity_Zoo:A#apx

Росс Снайдер
источник
1
Смотрите также qwiki.stanford.edu/wiki/Complexity_Zoo:G#glo, который, кажется, не упоминается в записи APX.
Юкка Суомела
Синтаксическая характеристика APX (упомянутая в записи зоопарка) особенно красива.
Суреш Венкат