Il existe de nombreux problèmes d'optimisation qui sont connus pour être durs NP, tels que le problème du vendeur de voyage, max-sat ou la recherche du nombre minimum chromatique de graphique. Compte tenu d'un problème de ce genre, je suis curieux de la complexité du problème suivant:
Compte tenu d'un problème d'optimisation du dur NP et d'une solution de candidate S, est la solution optimale au problème?
Intuitivement, il semble que cela puisse être co-np dur, car il est facile de réfuter une réponse à un problème d'optimisation en devinant une meilleure solution et en l'utilisant comme témoin, mais je n'ai aucune idée de la façon de montrer cela. En fait, je ne sais pas vraiment comment raisonner sur la complexité de ce problème.
Est-ce que quelqu'un connaît-il de bonnes limites inférieures sur la complexité de ce problème de décision? Savoir si cela était co-np dur, pSPACE-dur, etc. serait vraiment intéressant.
3 Réponses :
Problème du dur NP est "au moins aussi acharné que les problèmes les plus difficiles dans le NP".
Exemple de problème de NP-Dur: arrêt du problème (si le programme A peut arrêter ou non?) :)
Disons que vous avez une solution de candidate: "Non, le programme A ne peut pas arrêter". Nous savons que vous ne pouvez pas le vérifier - c'est indéciable.
Vous ne pouvez même pas vérifier si "oui, programmer des arrêts" - parce que cela peut prendre pour toujours, il est donc aussi indéciable.
Le problème d'arrêt n'est pas le NP-dur. Il est indécitable (en général). Mais comment vérifiez-vous qu'un itinéraire pour un vendeur de voyage est de la longueur minimale? Il est censé être vérifiable en temps polynomial.
Je sais que ce problème d'arrêt est indécitable. Je pensais que cela y a une inclusion - mon erreur.
Mais s'il s'agit de c. Il est censé être vérifiable dans le temps polynomial, mais seul la version de décision de TSP: "Y a-t-il une meilleure solution que n", où N est un nombre.
Corrigez-moi si je me trompe, mais j'avais l'impression que le problème d'arrêt est un NP difficile dans lequel aucun problème dans NP peut être réduit en temps polynomial. Vous n'avez pas besoin d'être dans NP pour être dure NP. Suis-je trompé à ce sujet?
Oui, vous n'avez pas besoin d'être dans NP pour être NP-dur. Et le problème de halte n'est pas le NP-dur car j'ai écrit auparavant.
Et être clair, le problème qui est dans le NP et le NP-Hard est NP-complet.
Euh, le problème d'arrêt est à la fois indéciable et np-dur. Ce n'est pas comme s'ils sont mutuellement exclusifs.
Donc, en ce qui concerne cette réponse, disant que dans le pire des cas, cela n'est pas indécitable ne dit pas grand chose. Il pourrait toujours être vrai que c'est Co-np complet, par exemple.
Il devrait être évident que l'arrêt est NP-dur: étant donné aucun problème dans NP, j'écris un programme que SystemAticaly essaie toutes les preuves possibles jusqu'à ce qu'il en trouve un qui prouve que la réponse est oui. Ensuite, j'utilise une solution au problème d'arrêt pour décider si ce programme s'arrête, ce qui prouve si la réponse est oui (si le programme s'arrête) ou non (si le programme ne s'arrête jamais). Être indécitable ne le rend pas np-dur. Être capable de résoudre tout problème dans NP (et de nombreux autres problèmes) le rend NP-dur.
Non, le problème d'arrêt est le NP-dur dans le sens qui est plus difficile que tout autre problème dans NP (par définition). Mais la déclaration «pouvant être capable de résoudre tout problème dans NP le rend NP-Hard» est faux. Aucune solution n'existe pour le problème d'arrêt, n'est pas difficile de le trouver, cela ne peut pas exister! Et sa preuve est logique. Donc, par définition est np-dur mais n'est pas np, il n'est donc pas complet. C'est indéciable.
Le terme "problème d'optimisation du dur" semble un peu trop large pour permettre une réponse satisfaisante.
Par exemple, je ne peux pas voir ce qui empêche les problèmes de décision d'être considérés comme des problèmes d'optimisation des NP-Dur - si Vous considérez, disons, le problème Max-CNF-SAT avec les solutions étant marqués comme étage (K / N), où K est le nombre de clauses satisfaites et n est le nombre total de clauses dans l'instance (qui est clairement calculable dans Temps polynomial), puis toute valorisation qui donne une 1 dans cette formule devra satisfaire toute la formule. Supposons donc que nous optimisons le plancher (k / n) et appelons cela le problème de l'optimisation du sol-CNF-SAT :) p>
Cela implique que vous puissiez réduire la tautologie audit problème d'optimisation - nier l'entrée et ajouter tout Solution Comme S. Vous pouvez même ajouter une variable factice pour vous assurer que la solution initiale est de 0 dans le problème de plancher CNF-SAT. La négation est polynomial dans le temps. P>
Puis si un solutionneur du problème proposé juge S à ne pas être optimal, il doit exister une valorisation qui donne un 1 selon notre fonction fabriquée et satisfait ainsi à toute la formule - à son tour, fournir une évaluation qui ne satisfait pas l'entrée originale à la tautologie. p>
en trompant légèrement (en utilisant un problème d'optimisation artificiellement conçu), nous avons établi le problème «est optimal» comme CO-NP-complet, car La tautologie est facilement montrée à être co-np-complète. P>
par votre propre argument Le problème de décision "est optimal" est co-np-dur, car comme témoin, vous n'avez besoin que d'une meilleure solution - Score S , marquez le témoin et comparez. P>
Je ne me sens pas vraiment très bon à propos de cette réduction, mais je ne peux pas m'améliorer facilement sur la classe de problèmes. Si vous avez besoin qu'il y ait des instances qui marquent arbitrairement élevée et non seulement {0, 1}, je pouvais simplement utiliser N * plancher (k / n). Une amélioration de la classe pourrait ne pas envisager un problème qu'un problème d'optimisation du NP-dur, si, pour chaque K, il existe une instance qui a au moins K Solutions qui marquent toutes différemment. P>
Je pense que je peux toujours me tromper à travers cela: P>
Considérons une réduction qui ajoute des variables nominales à l'entrée tautologie comme suit: P>
d1 && d2 && d3 ... && dN && (S)
Parce que S est une solution candidate; Étant donné qu'il n'y ait aucun autre S dans lequel S peut être prouvé être gourmand ou moins optimal que tout autre S., il doit être que S est à l'actuelle la solution la plus optimale pour le problème.
En supposant que la variante de décision du problème d'optimisation est NP-complète, vous avez décrit une preuve que la vérification des solutions optimales est dans ConP. La voie la plus directe vers une dureté durable serait une réduction polynomiale de plusieurs-une réduction d'un problème de conP-dur, mais une telle réduction aurait une période difficile à trouver une solution à vérifier. J'ai pris un cours de complexité au niveau des diplômés et pense que cela convient au cstheory.
Si l'optimisation était un problème de minimisation entier positif (c'est-à-dire que la réponse est toujours un entier positif), vous pouvez effectuer une recherche binaire à l'aide du vérificateur "isoptimal", et il semble donc que ce soit le NP-dur aussi ...
@Moron: Est-ce nécessairement le cas? Notez que le problème nécessite une solution candidate réelle, pas simplement sa "valeur".
@mhum: Je parlais du cas que la valeur est la solution (comme le nombre chromatique). Bien sûr, vous avez raison que, si vous avez besoin d'une coloration, cela ne fonctionnera pas.
@Moron: En effet, j'interprète la question comme indiquant une "solution" à, par exemple, un nombre chromatique faisait référence à une coloration réelle et non simplement le nombre chromatique lui-même. Je suis venu à cette interprétation de la part où l'asker utilise une solution devinée pour en déduire que ce problème est dans CO-NP.