Problèmes d'optimisation «NP-complet»

Je suis légèrement confus par une terminologie que j'ai rencontrée concernant la complexité des problèmes d'optimisation. Dans une classe d'algorithmes, j'ai eu le gros problème de parcimonie décrit comme NP-complet. Cependant, je ne sais pas exactement ce que signifie le terme NP-complet dans le contexte d'un problème d'optimisation. Cela signifie-t-il simplement que le problème de décision correspondant est NP-complet? Et cela signifie-t-il que le problème d'optimisation peut en fait être plus difficile (peut-être en dehors de NP)?

En particulier, je suis préoccupé par le fait que si un problème de décision NP-complet est vérifiable en temps polynomial, une solution à un problème d'optimisation correspondant ne semble pas être vérifiable en temps polynomial. Est-ce à dire que le problème n'est pas vraiment dans NP, ou la vérifiabilité polynomiale du temps n'est-elle qu'une caractéristique des problèmes de décision NP?

Une tentative de réponse partielle:

Les problèmes de décision ont déjà été étudiés pendant un certain temps avant que des problèmes d'optimisation ne se manifestent, dans le sens où ils sont traités du point de vue des algorithmes d'approximation.

Vous devez être prudent lorsque vous transférez les concepts des problèmes de décision. Cela peut être fait et une notion précise de complétude NP pour les problèmes d'optimisation peut être donnée. Regardez cette réponse . Elle est bien sûr différente de la complétude NP pour les problèmes de décision, mais elle est basée sur les mêmes idées (réductions).

Si vous êtes confronté à un problème d'optimisation qui ne permet pas une vérification avec une solution réalisable, vous ne pouvez pas faire grand-chose. C'est pourquoi on suppose généralement que:

• Nous pouvons vérifier efficacement si l'entrée est réellement une instance valide de notre problème d'optimisation.
• La taille des solutions possibles est bornée polynomialement par la taille des entrées.
• Nous pouvons vérifier efficacement si une solution est une solution réalisable de l'entrée.
• La valeur d'une solution peut être déterminée efficacement.

Sinon, il n'y a pas grand-chose à espérer.

La classe de complexité ne contient que des problèmes de décision par définition. Il n'y a donc aucun problème d'optimisation. Et la définition basée sur le vérificateur de vous mentionnez est spécifique à . Je ne l'ai pas rencontré avec des problèmes d'optimisation.$\mathrm{NP}$N P N P$\mathrm{NP}$$\mathrm{NP}$

Si vous voulez vérifier qu'une solution n'est pas seulement faisable, mais aussi optimale, je dirais que c'est aussi difficile que de résoudre le problème d'optimisation d'origine parce que, afin de réfuter une solution donnée faisable et éventuellement optimale comme non optimale, vous doivent donner une meilleure solution, ce qui pourrait vous obliger à trouver la vraie solution optimale.

Mais cela ne signifie pas que le problème d'optimisation est plus difficile. Voir cette réponse , qui dépend bien sûr des définitions précises.

La raison pour laquelle la plupart des problèmes d'optimisation peuvent être classés comme P, NP, NP-complet, etc., sont les conditions de Kuhn-Tucker. Je parlerai en termes de problèmes de programmation linéaire, mais le KTC s'applique à de nombreux autres problèmes d'optimisation. Pour chaque problème d'optimisation, il existe un double. Si le but du problème d'origine est de maximiser certaines fonctions, alors le double (généralement) a une fonction à minimiser. -versa. Si, et seulement si, une solution est faisable pour le primaire et le double, c'est une solution optimale pour les deux. (Techniquement, peut être l'une d'un grand nombre de solutions optimales qui donnent le même résultat.)

Donc, trouver une solution optimale à un problème d'optimisation équivaut à trouver une solution valide pour le primaire et le dual. Vous pouvez utiliser des algorithmes d'optimisation pour trouver cette solution, mais le processus global est une preuve d'existence.

• Si vous souhaitez passer de la minimisation à la maximisation, multipliez la fonction objectif par -1.