Dans leur article (p. 503) Garey et Johnson remarquent:
... il pourrait exister un problème NP-complet qui n'est ni NP-complet au sens fort ni résoluble par un algorithme pseudo-polynomial temporel ...
Quelqu'un connaît-il des problèmes avec les propriétés mentionnées ci-dessus?
Je pense que la réponse possible à cette question peut être une liste de problèmes NP-complets au sens ordinaire, de sorte qu'aucun algorithme pseudopolynomial n'est connu pour eux.
ds.algorithms
np-hardness
np
Oleksandr Bondarenko
la source
la source
Réponses:
Je ne sais pas si vous souhaitez entendre plus de détails sur mon commentaire sur votre question, mais voici quand même plus de détails.
Si P = NP, chaque problème dans NP peut être résolu en temps polynomial et donc en temps pseudo-polynomial, ce qui signifie qu'aucun problème ne satisfait votre exigence, comme Magnus l'a noté dans sa réponse. Supposons donc P ≠ NP dans le reste de cette réponse.
Parce que P ≠ NP, il existe un langage L ∈NP ∖ P qui n'est pas NP-complet (théorème de Ladner). Considérez le problème suivant:
Produit direct de la partition et de l'
instance L : m entiers positifs a 1 ,…, a m et k entiers b 1 ,…, b k ∈ {0,1}.
Question : Les deux éléments suivants tiennent-ils?
(1) Les m entiers a 1 ,…, a m forment une instance oui du problème de partition.
(2) Le k chaîne de bits b 1 ... b k appartient à L .
Suivant l'article de Garey et Johnson, définissez la fonction Longueur comme m + mlog max i a i ⌉ + k et la fonction Max comme max i a i .
Il est courant de vérifier (i) qu'il est NP-complet au sens faible, (ii) qu'il n'a pas d'algorithme pseudo-polynomial, et (iii) qu'il n'est pas NP-complet au fort sens.
(Conseils: (i) L'appartenance à NP découle du fait que le problème de partition et L sont tous deux dans NP. Pour la dureté NP, réduisez la partition à ce problème. (Ii) Construisez une transformation pseudo-polynomiale de L à ce problème. (iii) Construire une transformation pseudo-polynomiale de ce problème en L en utilisant le fait que la partition a un algorithme pseudo-polynomial-time.)
Le problème de partition n'a rien de spécial dans cette construction: vous pouvez utiliser votre problème préféré faiblement NP-complet avec un algorithme pseudo-polynomial.
la source
Je dirais que la réponse est clairement non (c'est-à-dire que personne ne sait), car personne ne sait si les problèmes NP-complets peuvent être résolus en temps polynomial , et encore moins en temps pseudo- polynomial. (Chaque algorithme polynomial est, bien sûr, pseudopolynomial.) Si vous pouvez trouver un problème dans NPC qui ne peut pas être résolu en temps pseudopolynomial, vous venez de prouver que P ≠ NP, donc je pense qu'il est prudent de dire que de tels exemples ne seront pas produit bientôt.
la source