Pourquoi les problèmes NP-complets n'ont-ils pas des ratios d'approximation similaires?

Étant donné que 2 problèmes NP-complets sont par définition réductibles l'un à l'autre, une solution à l'un d'eux peut donc être obtenue en utilisant une boîte noire résolvant l'autre, pourquoi n'ont-ils pas des ratios d'approximation similaires (en se référant à leurs homologues d'optimisation )? Je suppose qu'une dérive constante ou même polynomiale pourrait être comprise, mais nous avons le cas d'algorithmes d'approximation à facteur constant pour certains problèmes NP-complets et, d'autre part, d'autres problèmes qui ne peuvent même pas être approximés par un algorithme d'approximation à rapport polynomial , comme le TSP général? Je vous remercie

cc.complexity-theory approximation-algorithms reductions N27
la source

parce que les réductions de la boîte noire ne préservent que l'aspect OUI / NON des problèmes (de décision), pas la proximité des approximations.

Suresh Venkat

si je réduis 3SAT en couverture de sommets, alors la couverture de sommets de taille k implique une satisfiabilité et vice versa. Mais si j'obtiens une couverture de sommet de taille 2k, cela ne signifie pas que je peux satisfaire la moitié des clauses.

Suresh Venkat

Choisissez une réduction spécifique d'un problème NP-complet à un autre et essayez de l'étendre pour conserver les taux d'approximation. Vous verrez ce qui ne va pas.

Peter Shor

La réponse de Peter est vraiment la meilleure. Essayez-le et voyez ce qui se passe. Je pense que par scepticisme philosophique, vous voulez dire «je n'ai pas vraiment l'intuition». Parfois, la meilleure façon est d'essayer quelques exemples et de laisser croître l'intuition.

Suresh Venkat

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Jukka Suomela

Réponses:

Les réductions sont définies par rapport à la version décisionnelle des problèmes. Les ratios d'approximation pour leurs versions d'optimisation sont une question distincte, qui semble liée mais ne doit pas nécessairement l'être. Donc, pour répondre à votre question par une question, d'un point de vue philosophique, pourquoi devriez-vous vous attendre à ce que le PNJ de classe conserve les ratios d'approximation alors qu'il n'est pas défini par rapport à eux en premier lieu?

Lev Reyzin
la source

"Les réductions sont définies par rapport à la version décisionnelle des problèmes." Est-ce vrai pour, disons, les réductions Levin ?

MS Dousti

Vous avez raison, toutes les réductions ne sont pas définies dans les versions de décision, mais nous ne pouvons définir le PNJ qu'en termes de réductions de boîte noire, et je suppose que cela peut conduire à des débats sur la façon dont ces classes changent avec la réduction utilisée ... J'aurais dû dire "la classe NPC est définie pour les problèmes de décision." Ce n'est pas vraiment un argument précis, car nous pourrions même définir une classe de problèmes de décision dont les versions d'optimisation préservent les ratios d'approximation, mais ce n'est pas ce que nous faisons pour la classe NPC. Je suppose que la question de @ N27 étant une objection philosophique, je suis autorisé à donner une réponse philosophique. :)

Lev Reyzin