« Problème NP-complet » : historique des versions

14 janvier 2024

• actudiff 12:5714 janvier 2024 à 12:57‎ Jean-Christophe BENOIST discuter contributions‎ 20 505 octets +271‎ il faut tout de même dire quel est le problème général annuler
• actudiff 12:4914 janvier 2024 à 12:49‎ 109.0.238.201 discuter‎ 20 234 octets −265‎ Suppression d'une affirmation fausse, cf. version anglaise (il y a même des problèmes NP-complet qui se résolvent en exp(log^2(T)) (presque polynomial donc...) comme celui de l'hypercube vide d'aire maximale) annuler

12 janvier 2024

• actudiff 20:1912 janvier 2024 à 20:19‎ JulesROGUE discuter contributions‎ 20 499 octets +12‎ Fonctionnalité de suggestions de liens : 3 liens ajoutés. annuler Balises : Éditeur visuel Tâche pour novices Suggéré : ajouter des liens

25 mars 2023

• actudiff 11:5325 mars 2023 à 11:53‎ Antimuonium discuter contributions‎ 20 487 octets +96‎ Ajout confusion annuler

7 juin 2022

• actudiff 13:487 juin 2022 à 13:48‎ Psion007 discuter contributions‎ m 20 391 octets +12‎ Il manquaut 2 mots : en "fonction de" la taille annuler Balise : Éditeur visuel

16 mars 2021

• actudiff 18:4916 mars 2021 à 18:49‎ Dfeldmann discuter contributions‎ m 20 379 octets +12‎ →‎Contre-exemples annuler Balise : Éditeur visuel
• actudiff 18:4816 mars 2021 à 18:48‎ Dfeldmann discuter contributions‎ m 20 367 octets −3‎ →‎Définition formelle annuler Balise : Éditeur visuel

4 février 2020

• actudiff 18:244 février 2020 à 18:24‎ Mi Ga discuter contributions‎ 20 370 octets +37‎ Ajout annuler

27 avril 2019

• actudiff 15:2827 avril 2019 à 15:28‎ DSisyphBot discuter contributions‎ m 20 333 octets −5‎ Bot, transformation de liens avec le modèle {{Lien}} en lien interne, suite à la création de l'article correspondant annuler

18 octobre 2018

• actudiff 11:4918 octobre 2018 à 11:49‎ SniperMaské discuter contributions‎ m 20 338 octets 0‎ typographie (cf. « WP:TYPO#LISTES ») annuler

7 août 2018

• actudiff 18:497 août 2018 à 18:49‎ Cbyd discuter contributions‎ 20 338 octets +101‎ →‎Histoire : +1 images annuler

23 juillet 2018

• actudiff 02:2923 juillet 2018 à 02:29‎ Tfdyrtswa3w4se5dr discuter contributions‎ 20 237 octets +41‎ →‎Preuves de NP-complétude annuler Balises : Modification par mobile Modification par le web mobile

9 novembre 2017

• actudiff 16:329 novembre 2017 à 16:32‎ 37.168.184.109 discuter‎ 20 196 octets +4‎ Oubli d'un mot ("dans le pire cas" => "dans le pire des cas") annuler Balise : Éditeur visuel

17 juillet 2017

• actudiff 10:4917 juillet 2017 à 10:49‎ Fschwarzentruber discuter contributions‎ 20 192 octets +63‎ →‎Définition formelle : si si on sait. C'est le théorème de Ladner (1975) annuler Balise : Éditeur visuel

6 juillet 2017

• actudiff 20:116 juillet 2017 à 20:11‎ ManiacParisien discuter contributions‎ m 20 129 octets +14‎ + Larry J. Stockmeyer annuler

4 juillet 2017

• actudiff 19:234 juillet 2017 à 19:23‎ Roll-Morton discuter contributions‎ 20 115 octets −17‎ →‎Contre-exemples : meilleur lien annuler

4 janvier 2017

• actudiff 21:164 janvier 2017 à 21:16‎ TomT0m discuter contributions‎ 20 132 octets −44‎ Annulation des modifications 133331811 de Mourad1081 (d) non annuler
• actudiff 20:334 janvier 2017 à 20:33‎ Mourad1081 discuter contributions‎ m 20 176 octets +44‎ Il est préférable de souligner le fait que nous sommes dans NP si la solution en temps polynomial est une machine de Turing non-déterministe. Sinon, cela serait ambigu car la classe P possède également une solution polynomiale (TM déterministe). annuler Balise : Éditeur visuel

11 décembre 2016

• actudiff 13:2711 décembre 2016 à 13:27‎ PIerre.Lescanne discuter contributions‎ 20 132 octets −16‎ Annulation des modifications 132566428 de 88.190.109.130 (d) quand le problème est NP, ce n'est plus une question de rapidité annuler
• actudiff 01:0311 décembre 2016 à 01:03‎ 88.190.109.130 discuter‎ 20 148 octets +16‎ précision annuler Balise : Éditeur visuel

1 décembre 2016

• actudiff 02:531 décembre 2016 à 02:53‎ 201.183.143.85 discuter‎ 20 132 octets −166‎ C'était parfaitement clair, il faut avoir l'esprit tordu pour avoir interpréter "au moins aussi difficile" comme "aussi difficile ou moins difficile", c'est clairement "aussi difficile ou plus difficile" annuler

21 novembre 2016

• actudiff 09:2221 novembre 2016 à 09:22‎ ManiacParisien discuter contributions‎ m 20 298 octets +20‎ →‎Articles connexes : + Lien "Kernelisation" annuler

13 octobre 2016

• actudiff 08:4313 octobre 2016 à 08:43‎ Ftiercel discuter contributions‎ m 20 278 octets +166‎ Pas clair. annuler

30 mai 2016

• actudiff 22:4530 mai 2016 à 22:45‎ Fschwarzentruber discuter contributions‎ m 20 112 octets +5‎ →‎Contre-exemples annuler Balise : Éditeur visuel
• actudiff 22:4530 mai 2016 à 22:45‎ Fschwarzentruber discuter contributions‎ m 20 107 octets +1‎ →‎Contre-exemples annuler Balise : Éditeur visuel

31 mars 2016

• actudiff 10:4031 mars 2016 à 10:40‎ PIerre.Lescanne discuter contributions‎ 20 106 octets +8‎ →‎Histoire : refsou annuler

30 mars 2016

• actudiff 15:3030 mars 2016 à 15:30‎ Jean-Christophe BENOIST discuter contributions‎ 20 098 octets +1‎ NP=P n'est pas démontré annuler
• actudiff 15:1530 mars 2016 à 15:15‎ 46.218.26.82 discuter‎ 20 097 octets −1‎ remplacement de temps exponentiel par temps polynomial annuler Balise : Éditeur visuel

31 août 2015

• actudiff 08:5131 août 2015 à 08:51‎ Poulos discuter contributions‎ m 20 098 octets +14‎ Restauration des ancres brisées annuler

15 juillet 2015

• actudiff 16:3115 juillet 2015 à 16:31‎ Roll-Morton discuter contributions‎ m 20 084 octets +26‎ →‎Contre-exemples : +lien annuler

2 juillet 2015

• actudiff 17:392 juillet 2015 à 17:39‎ Roll-Morton discuter contributions‎ m 20 058 octets +11‎ ± Catégorie:Classe de complexité->Catégorie:Classe de complexité annuler Balise : HotCats
• actudiff 17:312 juillet 2015 à 17:31‎ Roll-Morton discuter contributions‎ m 20 047 octets −4‎ →‎Définition formelle : pour éviter le gras dans le texte annuler

13 juin 2015

• actudiff 07:2413 juin 2015 à 07:24‎ Poulos discuter contributions‎ m 20 051 octets +10‎ Restauration des ancres brisées annuler

12 janvier 2015

• actudiff 08:1212 janvier 2015 à 08:12‎ HerculeBot discuter contributions‎ m 20 041 octets −4‎ [Bot] : transformation de liens avec le modèle {{Lien}} en lien interne, suite à la création de l'article correspondant; changements de type cosmétique annuler

13 décembre 2014

• actudiff 23:0813 décembre 2014 à 23:08‎ SniperMaské discuter contributions‎ m 20 045 octets +2‎ →‎Méthodes approchées : typographie annuler
• actudiff 23:0513 décembre 2014 à 23:05‎ SniperMaské discuter contributions‎ m 20 043 octets +4‎ →‎Méthodes exactes : syntaxe + formatage annuler
• actudiff 23:0413 décembre 2014 à 23:04‎ SniperMaské discuter contributions‎ m 20 039 octets +7‎ →‎Liste de problèmes NP-complets : syntaxe + typographie + formatage annuler
• actudiff 18:3013 décembre 2014 à 18:30‎ SniperMaské discuter contributions‎ m 20 032 octets +2‎ syntaxe annuler
• actudiff 18:2913 décembre 2014 à 18:29‎ SniperMaské discuter contributions‎ m 20 030 octets −1‎ →‎Définition formelle : syntaxe annuler

17 novembre 2014

• actudiff 21:4817 novembre 2014 à 21:48‎ Roll-Morton discuter contributions‎ 20 031 octets −44‎ →‎Liste de problèmes NP-complets : voir pdd annuler

9 septembre 2014

• actudiff 18:169 septembre 2014 à 18:16‎ Roll-Morton discuter contributions‎ 20 075 octets +25‎ + lien (pê pas le plus pertinent) annuler

28 août 2014

• actudiff 10:2928 août 2014 à 10:29‎ Anne Bauval discuter contributions‎ m 20 050 octets +33‎ →‎Articles connexes : Conjecture des jeux uniques annuler

6 avril 2014

• actudiff 23:556 avril 2014 à 23:55‎ 141.218.35.129 discuter‎ 20 017 octets +9‎ Lien:Journal of Computer and System Sciences annuler

9 février 2014

• actudiff 02:579 février 2014 à 02:57‎ OrlodrimBot discuter contributions‎ m 20 008 octets −55‎ Retrait de l'outil de retour des lecteurs annuler

1 janvier 2014

• actudiff 22:541 janvier 2014 à 22:54‎ Piku discuter contributions‎ 20 063 octets +12‎ Introduction : voir homonymes annuler

6 novembre 2013

• actudiff 20:066 novembre 2013 à 20:06‎ Vlaam discuter contributions‎ m 20 051 octets +29‎ WPCleaner v1.30 - Homonymies : Correction de 1 lien - Heuristique annuler

6 août 2013

• actudiff 18:036 août 2013 à 18:03‎ Roll-Morton discuter contributions‎ m 20 022 octets +102‎ Aucun résumé des modifications annuler

26 juin 2013

• actudiff 17:5726 juin 2013 à 17:57‎ Gzen92 discuter contributions‎ m 19 920 octets +55‎ ajout Catégorie:Wikipédia:Outil de retour des lecteurs (prise_de_décision) annuler

23 mai 2013

• actudiff 17:4723 mai 2013 à 17:47‎ PIerre.Lescanne discuter contributions‎ 19 865 octets +44‎ Annulation des modifications 93332921 de Pparent (d) annuler

21 mai 2013

• actudiff 21:4121 mai 2013 à 21:41‎ Pparent discuter contributions‎ 19 821 octets −44‎ Les heuristiques ne donnent pas de solutions exactes. annuler