Est-ce une règle que les problèmes discrets sont durs NP et les problèmes continus ne le sont pas?

27

Dans ma formation en informatique, je remarque de plus en plus que la plupart des problèmes discrets sont NP-complets (au moins), alors que l'optimisation de problèmes continus est presque toujours facilement réalisable, généralement grâce à des techniques de gradient. Y a-t-il des exceptions à cela?

cc.complexity-theory co.combinatorics optimization alekdimi
la source

14

Il y en a sûrement, beaucoup. L'appariement bipartite et général, et les coupes min sont trois problèmes discrets résolvables polynomiaux en temps classique. De nombreux problèmes d'optimisation continue non convexe sont NP-difficiles: trouver le diamètre d'un ensemble convexe, ou calculer la norme injective d'un tenseur 3D.

Sasho Nikolov

6

Voici un problème d'optimisation continue simple qui est difficile à résoudre par NP

Jukka Suomela

8

Je ne sais pas quels problèmes vous avez en tête, mais de nombreux problèmes continus qui sont "résolus" par des méthodes de gradient ne sont pas vraiment "résolus": la méthode ne fait que trouver une sorte d'optima local.

Suresh Venkat

1

Jusqu'à présent, toutes les réponses semblent être des contre-exemples, mais il serait bon de voir certains cas où cette règle semble être vraie. Deux qui me viennent à l'esprit sont la programmation linéaire vs la programmation entière et l'optimisation convexe vs la maximisation sous-modulaire.

usul

13

Je pense que le tout discret vs continu est un hareng rouge. Un problème doit avoir une structure très spéciale pour être efficacement résoluble. Je pense que la vraie différence ici est que dans le cas de problèmes continus faciles, la structure spéciale a tendance à être la convexité, tandis que dans le cas de problèmes discrets faciles, les choses semblent plus compliquées: parfois, la structure est sous-modulaire ou intersection matroïde, mais souvent ce n'est pas le cas. Cela a probablement plus à voir avec le fait que nous ne comprenons pas encore très bien les mathématiques discrètes.

Sasho Nikolov

41

Un exemple que j'aime est le problème où, étant donné distincts , décidez si: $a_1, a_2, \ldots, a_n \in \mathbb{N}$

\int_{- π}^{π} \cos ({une}_{1} z) \cos ({une}_{2} z) \dots \cos ({une}_{n} z) ré z \neq 0

$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$

Cela semble au premier abord comme un problème continu pour évaluer cette intégrale, mais il est facile de montrer que cette intégrale n'est pas nulle s'il existe une partition équilibrée de l'ensemble , donc ce problème intégral est en fait NP-complet. $\{a_1, \ldots, a_n\}$

Bien sûr, j'encourage à jouer avec certains outils numériques pour vous convaincre que la plupart (sinon la totalité) des astuces numériques pour évaluer cette intégrale sont vouées à l'échec une fois que devient assez grand. $n$

Joe Bebel
la source

4

Puisque nous sommes sur le sujet, la première référence à ce problème que je peux trouver est dans "The Nature of Computation" de Moore et Mertens. Ils ne fournissent aucune référence, je suppose donc qu'ils l'ont inventé ou qu'il provient du folklore. J'apprécierais si quelqu'un connaît la source de ce problème.

Joe Bebel

Vraisemblablement non seulement la plupart mais toutes les techniques numériques évolueront de façon catastrophique pour un

assez grand ? Puisque le problème est NP-complet, une technique numérique précise pour évaluer l'intégrale qui a été mise à l'échelle polynomiale dans

serait suffisante pour montrer P = NP.

n

$n$

n

$n$

EP

1

À droite, un algorithme qui évalue toujours cette intégrale correctement dans le polynôme temporel dans

serait suffisant pour montrer P = NP. D'un autre côté, je ne peux pas exclure à 100% la possibilité de certaines techniques numériques que je ne connais pas bien en quelque sorte sur des instances spécifiques de cette intégrale, même lorsque

est grand, un peu comme la façon dont les solveurs SAT sont souvent capables pour trouver des affectations satisfaisantes pour certaines formules avec des milliers de variables, même si les performances les plus défavorables sont mauvaises. Donc, même si je doute que de telles méthodes existent, j'ai un peu couvert ma réponse.

n

$n$

n

$n$

Joe Bebel

3

Apparemment, la source originale de ce problème est: David Plaisted, Certains problèmes de divisibilité polynomiale et entière sont NP-difficiles. SIAM Journal on Computing, 7 (4): 458–464, 1978. La référence se trouve à l'arrière de Moore et Mertens, mais pas dans le corps du texte lui-même.

Joe Bebel

26

Il existe de nombreux problèmes continus de la forme "tester si cette entrée combinatoire peut être réalisée comme une structure géométrique" qui sont complets pour la théorie existentielle des réels , un analogue continu de NP. En particulier, cela implique que ces problèmes sont durs NP plutôt que résolus polynomialement. Les exemples incluent tester si un graphique donné est un graphique de distance unitaire, si un graphique donné peut être dessiné dans le plan avec des bords de segment de ligne droite et au plus un nombre donné de croisements, ou si un arrangement pseudoline donné peut être étiré pour former une ligne arrangement.

Il y a d'autres problèmes continus qui sont encore plus difficiles: par exemple, trouver un chemin le plus court parmi les obstacles polyédriques en 3D est PSPACE-complet (Canny & Reif, FOCS'87).

David Eppstein
la source

1

«Le chemin le plus court parmi les obstacles polyédriques» est continu de nom seulement, n'est-ce pas? Nous pouvons considérer l'espace de configuration comme l'union d'un certain nombre de pièces discrètes correspondant à des chemins qui «étreignent» un ensemble donné d'obstacles; alors l'optimisation locale à l'intérieur de chaque pièce donnée (c'est-à-dire à l'intérieur d'un ensemble d'obstacles donné) est simple, mais décider quel chemin a la meilleure distance au monde est la partie la plus difficile du problème.

Steven Stadnicki

13

Bien que cela ne réponde pas exactement à votre question initiale, c'est un exemple (conjectural) d'une sorte de contrepoint philosophique: un problème où la présentation est discrète mais toute la dureté vient de l'aspect `` continu '' du problème.

$A=\{a_1, a_2, \ldots, a_m\}$ $B=\{b_1, b_2, \ldots, b_n\}$ $\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$ difficile, on soupçonne largement qu'il peut être NP-dur et peut en fait être en dehors de NP (il y a, comme indiqué dans les commentaires, d'excellentes raisons de croire qu'il n'est pas NP-complet); le seul confinement connu à ce jour est plusieurs niveaux plus haut dans la hiérarchie polynomiale. Évidemment, la présentation de ce problème est aussi discrète que possible - un ensemble d'entiers et une question oui / non à leur sujet - mais le défi se pose parce que si le calcul des racines carrées avec une précision spécifiée est un problème facile, il peut être nécessaire de les calculer à une précision élevée (potentiellement superpolynomiale) pour régler l'inégalité d'une manière ou d'une autre. Il s'agit d'un problème «discret» qui surgit dans un nombre surprenant de contextes d'optimisation et contribue à contribuer à leur propre complexité.

Steven Stadnicki
la source

4

J'aime aussi beaucoup cet exemple, même s'il convient de souligner qu'il existe de bonnes raisons de croire qu'il n'est pas complet en NP; voir ( cstheory.stackexchange.com/a/4010/8985 )

Joe Bebel

@JoeBebel Très bon point - j'ai légèrement révisé ma langue pour refléter cela. Merci!

Steven Stadnicki

6

Les problèmes discrets ont généralement tendance à être plus difficiles (par exemple LP vs ILP), mais ce n'est pas la discrétion en soi qui est le problème ... c'est la façon dont les contraintes affectent la façon dont vous pouvez rechercher votre domaine. Par exemple, vous pouvez penser que l'optimisation d'un polynôme est quelque chose que vous pouvez faire efficacement, mais décider de la convexité des quartiques (polynômes de degré 4) est NP-difficile .

Ce qui signifie que même si vous avez déjà l'optimum, prouver simplement que vous êtes à l'optimum est déjà NP-difficile.

Mehrdad
la source

Je pense que la discrétion fait également partie du problème. Disons par exemple que vous auriez une variante ILP de LP. Vous pouvez par exemple viser à trouver la solution pour la variante LP, mais il y a encore des 2^n" voisins intéressants " que vous devez rechercher.

Willem Van Onsem

@CommuSoft: Pas vraiment ... la discrétion n'est pas le problème. Découvrez le problème de chemin le plus court , qui est un problème discret mais se réduit néanmoins à un cas particulier de programmation linéaire intégrale , qui est résolu dans le temps P (à ne pas confondre avec la programmation linéaire entière , qui est évidemment NP-difficile).

Mehrdad

ce n'est pas vraiment une surprise: puisque la programmation linéaire entière est NP-complète, chaque problème dans P (qui peut être résolu en temps poly), peut être transformé en temps poly dans un problème ILP.

Willem Van Onsem

@CommuSoft: Avez-vous lu entièrement le commentaire? Je ne parle pas d'ILP.

Mehrdad

désolé, lisez vite. Mais c'est parce que les contraintes sont totalement unimodulaires , donc seulement par la "grâce" de contraintes bien structurées, de tels problèmes sont faciles à résoudre. En général, la discrétisation est un aspect problématique des problèmes.

Willem Van Onsem

5

Bien que pour certains problèmes courants, il soit vrai, je pense que les deux hypothèses - en fonction de ce que vous définissez comme un problème d'optimisation - ne sont pas vraies.

D'abord quelques définitions: la plupart des problèmes d'optimisation ne font pas partie de NP . Par exemple pour le problème Knapsack : on ne peut pas exploiter le non-déterminisme pour construire le sac le plus précieux, simple car les différentes branches non déterministes n'ont pas de mémoire partagée. NP est également défini comme «polynomialement vérifiable» (vérification d'un certificat) [1, p. 34]. Dans ce cas, le certificat est par exemple un sac : une chaîne de bits où si le i- ème bit est défini, cela implique que le i- ème élément fait partie du sac. Vous pouvez en effet vérifier en temps polynomial si un tel sac est plus précieux qu'un seuil donné (c'est la variante de décision), mais vous ne pouvez pas - à notre connaissance - sur la base d'un seul sac, (un nombre polynomial de sacs), décider si ce sac est le plus précieux de tous les sacs possibles. C'est une différence essentielle entre, par exemple, NP et EXP : dans EXP , vous pouvez énumérer tous les sacs possibles et faire la comptabilité pour savoir quel sac est le meilleur.

le variante de décision des problèmes d'optimisation fait dans certains cas partie de NP , il faut faire une distinction claire entre l' arôme de maximisation et l' arôme de décision . Dans l'arôme décisionnel, la question est: " Étant donné un problème d'optimisation, et une utilité liée, existe-t-il une solution avec une utilité supérieure ou égale à cette limite " (ou légèrement modifiée pour un problème de minimisation).

Je suppose aussi que par NP - vous dire la partie (hypothétique) de NP qui ne fait pas partie de P . Si P = NP , bien sûr NP-complet existe toujours, mais il sera égal à P (ne coïncide avec P que pour certaines notions de réduction, comme les réductions de plusieurs à un temps polynomial par @ AndrásSalamon), ce qui n'est pas si impressionnant ( et réduirait l '" écart " que vous indiquez dans votre question).

Je constate de plus en plus que la plupart des problèmes discrets sont NP-complets.

Maintenant que nous avons réglé ça: il y a beaucoup de problèmes d'optimisation qui sont en P : problème de chemin le plus court , problème de débit maximal (pour les capacités intégrales), minimum spanning tree et correspondant au maximum . Bien que ces problèmes puissent vous sembler «triviaux à résoudre», ce sont toujours des problèmes d'optimisation, et dans de nombreux cas, la construction (et la preuve de leur exactitude) n'est pas si simple. La réclamation ne tient donc pas tous les problèmes discrets sont NP-complète. Étant donné que P n'est pas égal à NP , ces problèmes ne peuvent donc pas être NP-complets .

$\Sigma^P_i$

Alors que l'optimisation des problèmes continus est presque toujours facilement réalisable.

Un problème continu populaire qui est NP-difficile est la programmation quadratique .

En programmation quadratique, on cherche un vecteur $\vec{x}$ tel que:

\frac{{\vec{X}}^{T} \cdot Q \cdot \vec{X}}{2} + {\vec{c}}^{T} \cdot \vec{X}

$\dfrac{\vec{x}^T\cdot Q\cdot\vec{x}}{2}+\vec{c}^T\cdot\vec{x}$ est minimisé satisfaisant:

UNE \cdot \vec{X} \leq \vec{b}

$A\cdot\vec{x}\leq\vec{b}$

En fait, la programmation linéaire a longtemps été considérée comme NP-difficile , mais avec des heuristiques très performantes (la méthode Simplex ). L'algorithme de Karmarkar est cependant en P .

A partir du moment où le problème d'optimisation concerne des objets non convexes, il sera en général difficile - sinon impossible - de trouver un algorithme efficace.

Bibliographie

[1] Complexité informatique, une approche moderne , Sanjeev Arora et Boaz Barak

Willem Van Onsem
la source

2

Le paragraphe des définitions est en effet un peu confus. Le sac à dos est un problème d'optimisation NP. Il n'est pas vrai que "on ne sait pas" si la version d'optimisation est en NP: ce n'est pas le cas par définition. De plus, je ne pense pas que nous connaissions un problème qui soit NP-complet conditionnel à NP différent de PIe 3-SAT sera NP-complet même si P = NP (en fait, si P = NP, chaque problème dans P est NP complet).

Sasho Nikolov, le

@ AndrásSalamon: point pris. J'ai supprimé cette partie. C'était en effet un peu bâclé.

Willem Van Onsem du

@ AndrásSalamon: c'est évidemment vrai. Par conséquent, il dit: " Étant donné que P n'est pas égal à NP, ces problèmes ne peuvent donc pas être NP-complets. "

Willem Van Onsem

@ AndrásSalamon: Eh bien, si P=NPchaque problème dans NP-complete fait par définition partie de NP et donc en étendant P , maintenant P signifie qu'il existe un algorithme polynomial. Le fait est que je pense que la transformation n'a pas d'importance, car pour chaque langue en P, il doit exister un algorithme polynomial. Que vous preniez la transformation (tout au plus polynomiale) ou non, cela n'a pas d'importance. Il reste polynomiale, donc dans P . En d'autres termes, étant donné que l'élément d'origine est en P , vous pouvez prendre gratuitement chaque transformation poly-temps (sans entraîner une classe de complexité plus élevée).

Willem Van Onsem du

2

Le sac à dos en tant que problème d'optimisation n'est certainement pas complet en NP, car ce n'est pas un problème de décision, donc pas en NP. En tout cas, je comprends ce que vous dites, mais c'est le genre de détails de premier cycle qui, je pense, devraient être pris pour acquis sur un forum de niveau de recherche comme CStheory @ SE, tout comme je ne m'attends pas à voir une explication sur la façon dont la convergence en probabilité n'est pas la même chose que la convergence presque sûre sur Mathoverflow.

Sasho Nikolov

Est-ce une règle que les problèmes discrets sont durs NP et les problèmes continus ne le sont pas?

Réponses: