Pourquoi la programmation linéaire en P mais la programmation en entier NP-hard?

35

La programmation linéaire (LP) est en P et la programmation entière (IP) est NP-difficile. Mais comme les ordinateurs ne peuvent manipuler les nombres qu’avec une précision finie, un ordinateur utilise en pratique des entiers pour la programmation linéaire. Pour cette raison, LP et IP ne devraient-ils pas appartenir à la même classe de complexité?

complexity-theory polynomial-time Sasha le Noob
la source
7
Ajoutant un peu à la réponse de jmite: Il existe de nombreux cas dans lesquels les contraintes d’intégralité rendent le problème beaucoup plus difficile. Par exemple, le problème de sac à dos fractionnaire peut être résolu en temps polynomial, bien que le problème de sac à dos entier soit NP-Hard. Donc, ce n'est pas seulement quelque chose qui est vrai pour LP et IP.
user340082710
7
Même si nous considérons que les ordinateurs effectuent des opérations avec des entiers, cela ne signifie pas que la solution renvoyée est un entier; il peut être rationnel, c'est -à- dire un rapport de deux nombres entiers. Et cela donne beaucoup plus de flexibilité. Et bien sûr, nous ne pouvons pas toujours convertir une solution rationnelle en une solution réalisable pour la propriété intellectuelle. En général, la propriété intellectuelle aura plus de contraintes sur les variables que de simplement demander une solution intégrale. Pensez à un programme de entier. 0,1
megas
1
Ce n'est pas si difficile de manipuler les nombres avec une précision infinie si vous voulez, surtout quand ils sont rationnels. La précision finie est simplement une optimisation pour réduire les temps d'exécution.
2
@Hurkyl "Ce n'est pas si difficile de manipuler les nombres avec une précision infinie si vous voulez, surtout quand ils sont rationnels." Il existe un sous-ensemble strict de nombres réels, appelé nombres calculables, qui comprend des nombres rationnels + tels que sqrt (2), etc., et est défini comme l'ensemble des nombres calculables par une machine de Turing. Ceux qui n'y sont pas inclus ne peuvent pas, par définition, être manipulés par un ordinateur.
Sasha the Noob
1
@SashatheNoob Ce que vous dites n'est pas vraiment en contradiction avec ce que Hurkyl a dit. Les nombres calculables n'ont pas de limite maximale prédéfinie sur leur précision (il est arbitrairement réglé sur la valeur de votre choix à condition que la machine de turing ait suffisamment de mémoire, d'où une précision infinie). Pour dire que le sous-ensemble de nombres calculables comprend tous les nombres rationnels, vous admettez que les ordinateurs peuvent manipuler les nombres avec une précision infinie. (La déclaration de Hurkyl est absolument vraie. Le fait que la précision soit limitée pour certains types de données est simplement une optimisation.)
BrainSlugs83

Réponses:

9

Je ne peux pas commenter car cela nécessite 50 répétitions, mais certaines idées fausses sont répandues, en particulier le commentaire de Raphaël "En général, un domaine continu signifie qu'il n'y a pas de force brute (et pas d'heuristique intelligente pour l'accélérer)".

C'est absolument faux. Le point clé est en effet la convexité. Sauf quelques qualifications techniques de contrainte, minimiser une fonction convexe (ou maximiser une fonction concave) sur un ensemble convexe est essentiellement trivial, au sens de convergence temporelle polynomiale.

En gros, on pourrait dire qu'il y a une correspondance entre la convexité d'un problème d'optimisation "mathématique" et la viabilité d'algorithmes gloutons dans l'optimisation "informatique". C'est en ce sens qu'ils activent tous les deux les méthodes de recherche locales. Vous n'aurez jamais à revenir en arrière dans un algorithme glouton et vous ne regretterez jamais le sens de la descente dans un problème d'optimisation convexe. Des améliorations locales de la fonction objectif vous rapprocheront TOUJOURS de l’optimum global.

Ce n'est pas le cas dans le cas non convexe. Ici, il peut y avoir un minimum global, mais plusieurs minimums locaux auxquels un algorithme de descente local sera toujours tracé, de la même manière que les algorithmes gloutons le font lorsqu'ils sont appliqués à des problèmes NP. Parfois, ils trouvent le vrai optimum, la plupart du temps non.

Benjamin Lindqvist
la source
23

La réponse courte: parce que vous pouvez utiliser Integers pour simuler des booléens pour SAT , mais lorsque vous ne vous limitez pas à cela, vous ne pouvez pas réellement simuler SAT. Vous obtiendrez une réponse réalisable, mais cela n'aura plus aucune signification en ce qui concerne l'instance SAT que vous essayez de simuler.

La réponse difficile à cette question est que nous ne savons pas qu'ils ne font pas partie de la même classe de complexité. Personne n'a la preuve que . Si nous comprenions les raisons profondes pour lesquelles les problèmes étaient si différents, il faudrait comprendre pourquoi les classes de complexité étaient différentes, ce que nous ne faisons pas.P≠NP

jmite
la source
21

La raison pour laquelle la programmation linéaire est «efficace» est que l’espace de la solution peut être représenté par un seul polyèdre convexe. Si l’on essaie de trouver le sommet "le plus élevé" de ce polyèdre (on peut appliquer une transformation linéaire à tout problème de programmation linéaire pour faire en sorte que "hauteur" corresponde à la quantité à maximiser), puis on peut parcourir les arêtes le point culminant sans jamais avoir à descendre "en descente". Ce qui rend la programmation d’entiers «difficile», c’est qu’il n’ya pas d’espace de solution continu, mais qu’il existe de nombreux espaces de solution disjoints et qu’aucun moyen de travailler progressivement vers la solution optimale.

supercat
la source
2
Le mot clé ici est "convexity"
cody
1
Cette ascension n’est-elle pas la méthode du simplexe, dont aucune variante n’est polynomiale dans le pire des cas?
Jbapple
1
Il existe de nombreux problèmes plus faciles à résoudre dans des espaces discrets (ce qui permet des recherches discrètes) que dans des espaces continus.
Raphaël
@Raphael: pouvez-vous donner quelques exemples de tels problèmes? J'y ai pensé et je ne peux pas en proposer beaucoup.
Cody
@cody Trouver des maxima / minima de fonctions (unidimensionnelles), par exemple. Voir ici pour un exemple mignon qui ne sera disponible qu'après avoir constaté que nous pouvons réduire l'espace de recherche fini à un espace fini. Notez que les disques ont cette particularité: en notant qu'il suffit de prendre en compte les angles d'un polyèdre, nous obtenons un espace de recherche fini. En général, un domaine continu signifie qu'il n'y a pas de force brute (et pas d'heuristique intelligente pour l'accélérer).
Raphaël
3

Les autres réponses sont correctes, mais je les trouve un peu techniques. Supposons que vous ayez balayé (éliminé) une matrice et que vous recherchiez une solution. La matrice ressemble à ceci:

column x1 x2 x3 x4 x5 x6 | solution
-----------------------------------
       1           1  1  | 3
          1              | 1
             1     1     | 2
                2  1  1  | 1

En programmation linéaire, vous pouvez maintenant définir les colonnes non pivotantes (x5, x6) sur 0, x4 sur 0,5 et trouver une solution triviale. En programmation par nombres entiers, vous ne pouvez pas simplement définir les colonnes non pivot sur 0. La solution est plus difficile à trouver (NP-difficile). Notez également que les solutions sont en , donc cela n’est pas directement lié à la précision finie / infinie.Q

Albert Hendriks
la source