Mark Dominus a rassemblé quelques exemples de réduction du temps polynomial de divers problèmes NP-difficiles à la correspondance «d'expression régulière» . Envisager des vérifications en temps polynomial n'est pas un énorme pas en avant.
Comment illustrez-vous la classe NP-complete aux étudiants de premier cycle ou aux amis d'autres domaines qui souhaitaient comprendre le remue-ménage récent provoqué par le papier de Deolalikar?
np-hardness
big-list
Greg Bacon
la source
la source
Quelques problèmes quotidiens difficiles à résoudre, formulés de manière appropriée:
Affecter des classes universitaires à des intervalles de temps afin de minimiser les conflits d'horaire.
Assigner les invités au mariage de manière à ce que les amis s’assoient à la même table, mais pas les ennemis.
Planifier un voyage sur la route pour visiter tous les sites touristiques figurant sur une liste, afin de minimiser la conduite.
la source
Le problème du voyageur de commerce est apparemment accessible ... du moins où je suis, il semble être de loin le problème le plus populaire chez les non-CS. J'ai également trouvé l'illustration suivante de Vertex Cover assez attrayante, telle que présentée par mon instructeur en algorithmes:
Vous avez un réseau routier et vous souhaitez vous assurer que si une voiture est en panne de carburant, il y a une station-service au moins à une extrémité de la route.
En tant qu'urbaniste, vous souhaitez minimiser les coûts en construisant le plus petit nombre possible de stations-service. C’est essentiellement le problème de la couverture de vertex, et j’ai réussi à souligner que, même si vous ne vous attendez pas à trouver la couverture de vertex optimale en temps polynomial, vous pouvez trouver un facteur deux plus petit en temps polynomial, en sélectionnant simplement les deux extrémités d'une correspondance maximale (eh bien, ce dernier détail peut être omis en fonction de votre audience - en particulier parce que l'algorithme MM n'est pas exactement à deux lignes).
En ce qui concerne un exemple de «saut dans la complexité» avec un léger changement dans la nature du problème, je pense que la différence entre la vérification de la colorabilité 2 et de la colorabilité 3 en est un bon exemple. Avec toute la publicité entourant le théorème des quatre couleurs, on peut également souligner qu'il est difficile de vérifier si une carte peut être colorée correctement avec seulement trois couleurs au lieu de quatre, même si nous savons qu'elle peut toujours être colorée avec quatre couleurs. Un bon nombre de personnes trouvent cela assez surprenant.
Une autre situation assez naturelle est le problème de reprise dans l’ impasse dans les systèmes d’exploitation. Ceci est modélisé par le problème NP-complet d'ensembles de sommets à réaction - le plus petit nombre de sommets dont la suppression rend le graphe acyclique - et je trouve que c'est aussi un exemple remarquable (et est expliqué plus en détail dans cet article de Wikipédia).
la source
Je pense que le stationnement parallèle est NP-difficile.
En fait, le problème plus général qui consiste à trouver le chemin le plus court avec une courbure limitée qui emmène un objet polygonal de sa position initiale à sa position finale dans un environnement polygonal est NP-difficile. La preuve peut être trouvée ici - http://portal.acm.org/citation.cfm?id=298976
la source
Knapsack est assez facile à saisir, en particulier pour ceux qui ont eu affaire à une petite valise… un bel exemple s’ils connaissent la programmation dynamique.
Un autre amusement (pratiquement identique) est Subset-sum, car il possède également une interprétation physique agréable: imaginez que les nombres sont les distances égales de points-masses sur une règle idéale (sans masse), avec le point d'appui à l'origine. Sous-ensemble-somme dit: existe-t-il un sous-ensemble non vide tel que la règle reste équilibrée? (c.-à-d. que le centre de gravité est le point d'appui de la règle?)
Dans les deux cas, il semble intuitif que des stratégies naïves puissent forcer le recours à la vérification de tous les sous-ensembles.
S'ils ont plus de connaissances en arrière-plan, il est agréable de développer des problèmes en supprimant des contraintes. Par exemple, en partant d'un problème de débit maximal, en le transformant en programme linéaire et en en faisant un programme entier. (Un bon exemple est bien sûr MAX-CUT, car pour les personnes plus expérimentées, vous pouvez également évoquer le CGU; je touche à cela dans une réponse MO, https://mathoverflow.net/questions/33036/is-quadratic-programming Si vous avez des limites et un point réalisable / 33048 # 33048. ) Il y a aussi des choses bien ordonnées comme des problèmes apparemment similaires qui ont une complexité très différente (le chemin d'Euler (bord) est linéaire temps, le chemin hamiltonien (sommet) est NP-complet).
la source
La construction de mots croisés est NP-complète: à partir d'un ensemble de réponses, essayez de les intégrer dans une grille.
la source
J'ai créé le site Web Tagxedo, http://www.tagxedo.com , un générateur de nuages de mots qui adapte les mots (classés par leur fréquence) à leur forme. Les résultats sont très jolis, mais il est facile de prouver que le problème est NP-difficile (problème de conditionnement).
Fait intéressant, de nombreux problèmes NP-difficiles ont des approximations "faciles". Tagxedo semble faire un travail presque parfait dans de nombreux cas. Cela conduit à une discussion intéressante sur l'implication pratique de P vs NP et le sujet de l'approximation.
la source
Un de mes amis a passé une année sabbatique à regarder un match de baseball dans tous les grands stades de ligues en Amérique du Nord. Sans voler. (Il n'a pas tout à fait réussi; trois stades étaient en construction cette année-là.)
la source
En raison du succès d'entreprises comme Uber et Lyft, de nombreuses personnes ont une expérience directe très accessible des problèmes NP-complete.
Ce problème (lorsqu'il est correctement reformulé) est un PNJ et j'imagine que des personnes se sont demandé à un moment donné comment Uber avait décidé d'associer conducteurs et passagers.
la source
J'utilise habituellement SAT comme exemple. Je dis quelque chose comme "toutes sortes de problèmes qui surgissent tout le temps peuvent être réécrites en cherchant une véritable affectation à une grande formule logique. La question P vs NP est de savoir s'il existe un moyen fondamentalement plus simple de résoudre cette formule logique essayer toutes les possibilités. Jusqu'à présent, personne n'a été capable de trouver un moyen ou de prouver qu'il n'existe pas de moyen facile de sortir ".
la source
Un problème de type Np-complet tel que Sudoku (sur nxn sqaure) est un outil universel qui nous permet de résoudre efficacement tous les problèmes pour lesquels des solutions vérifiables de manière efficace. La seule exigence est d'avoir une méthode efficace pour résoudre le sudoku.
la source
J'espère que cela t'aides!
la source
Un exemple accessible de manière fantaisiste est une brève présentation de Mark Dominus (voir le billet de blog connexe ) intitulée «Mon problème NP-complet préféré», où l'image ci-dessous est le trait de frappe d'un aperçu de la couverture exacte par 3 jeux .
Les titres de la série de vidéos incluent
L'intention était clairement que chaque vidéo contienne trois épisodes, tous sur un thème commun, issus d'un ensemble de sujets d'intérêt pour les jeunes enfants.
Le canard étrange de la série était une vidéo sur «les fleurs, les bananes et… les cheveux».
la source
Ce problème NP-complet pourrait s’avérer particulièrement utile si l’on examine ultérieurement le problème du sac à dos:
Nombre de devinettes, où vous ne pouvez deviner que des nombres simples jusqu'à ce que vous ayez bien compris.
la source