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

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 ³ ). 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.

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 $P$$Q$$f$$q$$Q$$P$$q$P f ( q ) $Q \iff f(q)$$P$$f(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 $f$$P$$P$

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.

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

Considérez cette IP, par exemple, étant donné $a_i \geq 0$ pour $i \in [1..n]$ :

$\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$

st et pour .$\quad\displaystyle\sum_{i=1}^n x_i \geq 1$xi∈Ni∈[1 ..n]
$\ \displaystyle x_i \in \mathbb{N}$$i \in [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.$a_1, \dots, a_n$$x_i=1$$n$

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.

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.

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