Comment le problème du voyageur de commerce est-il vérifiable en temps polynomial?

Je comprends donc l'idée que le problème de décision est défini comme

Existe-t-il un chemin P tel que le coût soit inférieur à C?

et vous pouvez facilement vérifier que cela est vrai en vérifiant le chemin que vous recevez.

Cependant, que se passe-t-il s'il n'y a pas de chemin qui correspond à ces critères? Comment vérifieriez-vous la réponse «non» sans résoudre le problème du meilleur chemin TSP et découvrir que le meilleur a un coût pire que C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
la source

Personnellement, je n'avais entendu que la classe NP signifiait la vérification de poly-temps, mais je n'avais jamais vu la restriction que cela signifie seulement vérifier les réponses de "oui, voici la solution". Il semble intuitif d'imaginer que vous devez pouvoir vérifier n'importe quelle solution en poly-temps.

wjmccann

Réponses:

NP est la classe de problèmes où vous pouvez vérifier les instances "oui". Aucune garantie n'est donnée que vous pouvez vérifier les «non» instances.

$C$

Il existe certains problèmes, tels que la factorisation entière et tout problème dans P , que nous savons être à la fois dans NP et co-NP . (Merci à user21820 de l' avoir signalé.)

On ne sait pas si NP et co-NP sont le même ensemble de problèmes. S'ils sont identiques, nous pouvons vérifier les instances "oui" et "non" de TSP. S'ils sont différents, alors P $\,\neq\,$ NP , puisque nous savons que P $\,=\,$ co-P (parce que nous pouvons simplement nier la réponse d'une machine déterministe, donnant la réponse au problème du complément).

David Richerby
la source

Il peut être utile de mentionner que nous connaissons certains problèmes qui sont à la fois dans NP et coNP, mais que nous ne savons pas s'ils sont dans P ou non, comme la factorisation entière.

user21820

@ user21820 La factorisation entière n'est pas un problème de décision. La primauté est un problème de décision et pendant des années, elle était connue à la fois en NP et en co-NP . Finalement , il a été démontré que dans P ainsi. Je ne sais pas s'il y a encore des problèmes connus pour être à la fois NP et co-NP sans avoir été démontré dans P .

kasperd

@kasperd: C'est un fait bien connu que la factorisation entière lorsqu'elle est transformée en un problème de décision (n a-t-elle un facteur premier inférieur à m?) est à la fois dans NP et coNP (les deux instances oui / non peuvent être vérifiées en temps polynomial via le test de primalité AKS étant donné la factorisation principale comme certificat), mais il n'est pas encore démontré qu'il est en P.

user21820

@ user21820 Il existe des moyens beaucoup plus simples et plus rapides de vérifier une factorisation que AKS.

kasperd

@kasperd: Je serais curieux de voir ceci ici. Pour vérifier une factorisation, il vous faudrait par exemple les facteurs premiers et pour chaque facteur premier une preuve qu'il est premier.

gnasher729

"Comment le problème du voyageur de commerce est-il vérifiable en temps polynomial?"

Soit de la manière que vous décrivez, soit il n'y a pas de telle manière connue.

"Cependant, que se passe-t-il s'il n'y a pas de chemin qui correspond à ces critères?"

Dans ce cas, pour toutes les machines NP pour le problème de décision, la machine retournera non pour tous les candidats-certificats.

"Comment vérifieriez-vous la réponse" non "sans résoudre le problème du meilleur chemin TSP et découvrir que le meilleur a un coût pire que C?"

Eh bien, on pourrait recevoir une preuve interactive qu'il n'y a pas de tels chemins .

Le problème que vous décrivez, TSP, n'est pas connu pour être dans le coNP , donc il n'y a pas de moyen connu de "NP-like" de vérifier qu'il n'y a pas un tel chemin.

Juho
la source