L'APX est-il contenu dans NP?

15

On dit qu'un problème P est dans APX s'il existe une constante c> 0 telle qu'un algorithme d'approximation polynomiale en temps existe pour P avec le facteur d'approximation 1 + c.

APX contient PTAS (vu en choisissant simplement n'importe quelle constante c> 0) et P.

APX est-il dans NP? En particulier, l'existence d'un algorithme d'approximation du temps polynomial pour un facteur d'approximation implique-t-elle que le problème est en NP?

cc.complexity-theory complexity-classes apx Andrew W.
la source
Je pense que "ce que l'on sait de la classe X par rapport à toutes les autres classes Y" est beaucoup trop vague comme question, à moins que d'autres détails ne soient fournis sur les types de relations recherchées.
András Salamon
Je veux dire des relations telles que «contient», «est contenu dans», «ne contient pas».
Andrew W.19
Après réflexion, j'ai limité la question à la relation spécifique qui m'intéresse le plus.
Andrew W.
1
Que signifie exactement demander si APX est contenu dans NP? APX se compose de problèmes "d'optimisation NP" approximatifs tandis que NP se compose de problèmes de décision. De plus, par définition, la version décisionnelle d'un problème d'optimisation NP est en NP. Peut-être que vous aviez autre chose en tête?
Joshua Grochow
Tu as raison Joshua. Ian a répondu à la question que j'aurais dû poser.
Andrew W.19

Réponses:

20

APX est défini comme un sous-ensemble de NPO, donc oui, si un problème d'optimisation est dans APX alors le problème de décision correspondant est dans NP.

Cependant, si ce que vous demandez est de savoir si un problème arbitraire doit se trouver dans NP (ou NPO) s'il y a une approximation du temps O (1), alors la réponse est non. Je ne connais pas de problèmes naturels qui servent de contre-exemple, mais on pourrait définir un problème de maximisation artificielle où l'objectif est la somme de deux termes, un grand terme qui est facilement optimisé en P, et un terme beaucoup plus petit cela ajoute une petite quantité si une partie de la solution code une réponse à un problème difficile (en dehors de NP). Ensuite, vous pourriez trouver, disons, une approximation 2 en temps poly en vous concentrant sur le terme facile, mais trouver une solution optimale nécessiterait de résoudre le problème difficile.

Ian
la source
2
J'ai accepté votre réponse car elle répondait à la fois à la question que j'ai posée (`` L'APX est-elle contenue dans NP? '') Et à la question que j'aurais dû poser (`` Est-ce qu'un O-1 poly-temps implique une solution exacte dans NP?
Andrew W.19
1
Une large classe de problèmes qui ne sont pas contenus dans NPO et NP mais qui ont une approximation à facteur constant est la classe des problèmes en ligne (la question de savoir quelle classe de complexité contient les problèmes en ligne est ici cstheory.stackexchange.com/questions/1664/… ) .
Oleksandr Bondarenko du