Tous les problèmes de programmation linéaire entière sont-ils NP-difficiles?

11

Si je comprends bien, le problème d'affectation est en P car l'algorithme hongrois peut le résoudre en temps polynomial - O (n 3 ). Je comprends également que le problème d'affectation est un problème de programmation linéaire entier , mais la page Wikipedia indique que c'est NP-Hard. Pour moi, cela implique que le problème d'affectation est en NP-Hard.

Mais le problème d'affectation ne peut certainement pas être à la fois dans P et NP-Hard, sinon P serait égal à NP? La page Wikipedia signifie-t-elle simplement que l'algorithme général pour résoudre tous les problèmes ILP est NP-Hard? Quelques autres sources affirment que l'ILP est NP-difficile, ce qui est vraiment déroutant dans ma compréhension des classes de complexité en général.

Mat
la source
4
NP-hard signifie que (à moins que P = NP), chaque algorithme déterministe polytime échoue sur un ensemble (infini) d'instances. Il existe généralement également des ensembles d'instances faciles.
Sasho Nikolov
1
Notez que l'énoncé n'est pas "chaque IP est NP-hard" mais "résoudre chaque IP est NP-hard".
Raphael
1
À titre de remarque, IP pour la dimension fixe est en P.
A.Schulz

Réponses:

20

Si un problème est NP-Hard, cela signifie qu'il existe une classe d'instances de ce problème qui sont NP-Hard. Il est parfaitement possible que d'autres classes spécifiques d'instances soient résolubles en temps polynomial.

Considérons par exemple le problème de trouver une 3-coloration d'un graphique . C'est un problème NP-Hard bien connu. Imaginez maintenant que ses instances soient limitées à des graphiques qui sont, par exemple, des arbres. Il est clair que vous pouvez facilement trouver une 3-coloration d'un arbre en temps polynomial (en effet, vous pouvez également trouver une 2-coloration).

Considérez les problèmes de décision pendant une seconde. Une méthode pour prouver la dureté d'un problème de décision consiste à concevoir une réduction polynomiale (Karp) à partir d'un autre problème connu pour être NP-difficile. Dans cette réduction , vous montrer qu'il existe une fonction qui associe chaque instance du problème à une instance du problème tel que: est une instance de oui pour est une instance de oui pour . Cela implique que la résolution de doit être "au moins aussi difficile" que la résolution de elle-même.Q f q Q P q QPQfqQPqP f ( q ) qQf(q)Pf(q)q

Remarquez comment il est pas nécessaire pour l'image de soit égale à l'ensemble des instances de . Par conséquent, il est parfaitement possible que le problème limité à un sous-ensemble d'instances ne soit pas difficile.P PfPP

Pour revenir à votre question d'origine:

  • Le problème d'affectation peut être résolu en temps polynomial, c'est-à-dire qu'une solution à chaque instance du problème d'affectation peut être calculée en temps polynomial.
  • ILP est NP-Hard: en général, il peut être difficile de calculer une solution à un problème ILP, c'est-à-dire qu'il existe des instances d'ILP qui sont dures.
  • Certaines instances spécifiques d'ILP peuvent être résolues en temps polynomial.
Steven
la source
Pourriez-vous expliquer s'il est nécessaire que mappe chaque instance de Q ne pouvons-nous pas mapper un sous-ensemble de Q ? c'est-à-dire que la pré-image de f doit être la totalité de Q ? fQQfQ
Mat
Il ne faut pas pour à la carte chaque instance de Q tant qu'il mappe une classe d'instances difficiles de (de l' infini) Q . Par exemple, afin de montrer que P est NP-dur, on peut fournir une réduction du problème de 3 couleurs limité aux graphes plans. fQQP
Steven
14

Non, les cas spéciaux peuvent être plus faciles.

Considérez cette IP, par exemple, étant donné ai0 pour i[1..n] :

mini=1nxiai

st et pour .i=1nxi1xiNi[1 ..n]
 xiNi[1..n]

Il trouve le minimum parmi (celui pour lequel, forcément, dans une solution optimale). Trouver le minimum de nombres est clairement un problème polynomial.a1,,anxi=1n

Raphael
la source
0

Vous pouvez modéliser un problème polynomialement résolu en IP. Cela ne signifie pas que le problème est NP-difficile. Cela signifie simplement qu'il n'y a pas d'algorithme polynomial connu pour résoudre le modèle IP de votre problème (sauf P = NP).

Donc, comme vous l'avez suggéré, le problème d'affectation est en P mais votre modèle IP est NP-difficile.

Austen
la source
3
L'IP dans la réponse de Raphaël peut être résolu en temps polynomial. En d'autres termes, en général, nous ne connaissons pas d'algorithme rapide pour résoudre les IP, mais il existe des cas particuliers de problèmes IP pour lesquels nous avons des algorithmes rapides.
Juho
0

Non, il existe un type spécial de programme entier, si la matrice de contraintes est TUM (matrice totalement unimodulaire), alors elle peut être assouplie dans le programme linéaire, qui peut être résolue en temps polynomial.

Jianhao Ma
la source
-4

Le problème d'affectation n'est pas un ILP, mais un problème LP et donc pas NP-hard.

Julia
la source
4
Je ne sais pas pourquoi vous pensez que le problème d'affectation n'est pas un ILP. Il se trouve que, dans ce cas, la solution optimale au programme linéaire est également la solution optimale au programme linéaire entier ... mais cela ne signifie pas que ce n'est pas une instance d'ILP.
DW
De plus, les instances individuelles ne sont jamais isolées en NP. Vous voulez dire "c'est en fait une instance facile", mais c'est une déclaration beaucoup plus compliquée (définissez "facile").
Raphael