Discussion:Théorie de la complexité (informatique théorique)

Définitions de C-complets et C-difficile

La différence entre C-complets et C-difficile me semble complètement fausse, et différente par exemple de la version anglophone. Un problème P est C-complet si tout les problèmes de C peuvent être réduit à P. Si de plus P est lui même dans la classe C, alors P est C-complet. De manière générale, le paragraphe 4 ne me semble pas bien clair. Laurent Vibert 12 novembre 2009 à 16:37 (CET)

Erreurs

Citation:

Le problème P = NP revient à savoir si on peut résoudre un problème NP-Complet avec un algorithme polynomial. Les problèmes étant tous classés les uns à partir des autres — un problème est NP-Complet si l'on peut réduire un problème NP-Complet connu en ce problème —, faire tomber un seul de ces problèmes dans la classe P fait tomber l'ensemble de la classe NP, ces problèmes étant massivement utilisés, en raison de leur difficulté, par l'industrie, notamment en cryptographie — cf. la factorisation en nombres premiers). Ceci fait qu'on conjecture cependant que les problèmes NP-complets ne sont pas solubles en un temps polynomial. À partir de là plusieurs approches sont tentées :

le problème de la factorisation en nombres premiers n'est pas connu comme un problème NP-complet (mais on pense qu'il n'est pas dans P pour autant. Plus précisément il est connu pour être à la fois dans NP et co-NP, ce qui rend improbable qu'il soit NP-complet, car alors on aurait NP inclus dans co-NP) — Le message qui précède, non signé, a été déposé par 17:44 147.171.255.200 (discuter), le 6 novembre 2007

Merci d'avoir signalé cette erreur. Bien sûr la factorisation d'un nombre est considérée comme très dure (elle est pour cela à la base de RSA), mais n'est pas un problème NP-complet. D'autre part, l'article manque totalement de pédagogie et a une structure un peu abrupte. Je l'ai donc mis en ébauche. Pierre de Lyon 7 novembre 2007 à 10:57 (CET)

Citation:

"On qualifie de NP-complets les problèmes décisionnels, c'est-à-dire ceux dont la réponse est de type binaire (oui/non, vrai/faux, 1/0, …). On qualifie de NP-difficiles les problèmes d'optimisation, c'est-à-dire que la réponse est de type numérique. À un problème d'optimisation NP-difficile est associé un problème de décision NP-complet, mais dire qu'un problème NP-difficile est aussi NP-complet est un abus de langage."

Je pense qu'il y a une confusion entre NP-complet et NP-difficile. Les deux classes concernent des problèmes de décisions. NP-difficile : existence d'une reduction polynomiale ..., NP-complet : problème à la fois NP-difficile et NP. (voir page dédiée : Problème_NP-complet).

Définitions des machines non-déterministes et à oracle

Il me semble qu'il y a un (plusieurs) problème dans l'article tel qu'il est actuellement dans la définition de machine non-déterministe:

les machines de Turing non-déterministes peuvent effectuer un nombre illimité d'opérations à la fois: c'est semi-vrai au mieux, et comme c'est la seule caractérisation qu'on en donne, on ne comprend pas comment on peut faire de la complexité sur de telles machines, dépourvues de limites.

Et elles ne sont pas aussi appelées machines à oracles: les deux notions sont complètement orthogonales. Les machines à oracle ont elles aussi leur importance en théorie de la complexité (pour définir la hiérarchie polynomiale), mais elles ne sont pas nécessaires pour ce qui est évoqué dans l'article pour l'instant. Je les retire donc pour le moment.

Il reste les deux autres détails qui me font douter aussi, et dont je ne pense pas qu'ils ajoutent à la clarté de l'article: je ne crois pas que la génération de nombres aléatoires ait quoi que ce soit à faire avec la théorie de la complexité, à moins de parler des classes aléatoires comme RP, BPP et les autres, et encore, au moins dans les définitions que j'en connais, on ne parle pas de générateur aléatoire mais de machine non-déterministe dont on compte les chemins acceptants.

Enfin, les machines à ADN auraient à mon avis plus à faire dans un paragraphe les autres notions de complexité et les modèles de calcul exotiques que dans celui-là, mais comme je ne sais pas trop comment le présenter, je laisse en l'état.

Galbolle 26 septembre 2006 à 13:42 (CEST)

Problème de réduction

La définition de réduction n'est pas claire : Un problème est C-dur (ou C-difficile) si ce problème est plus dur que tous problèmes dans C. Formellement on définit une notion de réduction : soient p et q deux problèmes, p se réduit à q si p est une instance de q. Et donc p est C-dur (ou C-difficile) si pour tout problème q de C, q se réduit à p. Ce si p est une instance de q est bizard. La notion de réduction est une notion de réécriture en temps polynomial (dans le cas des problèmes NP-dur) pour se ramener à une instance du problème q. Koko90 20 mar 2005 à 21:11 (CET)

Et l'usage d'inclusion stricte pour la hiérachie des classes (partie "Polynomial contre non polynomial") pose problème. On devrait mettre des "inclus ou égale" ce qui n'engage à rien... La plus part de ces inclusions strictes sont des conjectures. Koko90 20 mar 2005 à 21:17 (CET)

Bah vas-y, modifie ! Tom 25 mar 2005 à 09:58 (CET)

Par définition l'inclusion contient le cas d'égalité. C'est lorque l'inclusion est stricte qu'il est nécessaire de le préciser.

Définition circulaire

"Un problème est NP-Complet si il est dans NP, et si n'importe quel problème NP-Complet peut se réécrire à l'aide d'un algorithme polynomial comme un sous ensemble d'instance de ce problème".

Définir "NP-Complet" en utilisant le terme "NP-Complet", ça fait plutôt désordre, non ? :oD

François-Dominique 21 aoû 2004 à 09:18 (CEST)

Effectivement! En fait pour qu'un problème soit NP-Complet, il faut qu'il soit dans NP et que n'importe quel autre problème de la classe NP puisse se réécrire comme un sous-ensemble d'instance de ce problème. Et non pas tout les NP-Complet.

Enfin si : tout problème NP, donc a fortiori tout problème NP-Complet peut se ramener à tout autre problème NP-Complet. Mais c'est une conséquence de la définition. --Ąļḋøø 19 nov 2004 à 21:20 (CET)

En effet, s'il s'avérait que P = NP, alors on pourrait résoudre tous les problèmes NP en un temps polynomial sur une machine déterministe

Je ne sais pas si c'est vraiment la peine de preciser "sur une machine déterministe", est ce qu'il ne va pas de soit que tout ce qui est fait actuelment en informatique l'est pour ce qui a été dénomé plus haut "machine deterministe? Toutes les notions de complexité sont bassée sur le modèle de la machine de turing... Donc dans tout les cas je pense qu'il vaut mieux parler de machine de turing plutot que de machines deterministes. --as4 4 déc 2004 à 20:17 (CET)

Il y a peut être une manière plus habile de le dire. Mais la version précédente, qui ne précisait pas cela, n'était pas correcte : un algorithme NP est en effet un algorithme polynômial (mais pas forcément sur une machine déterministe).--Ąļḋøø 5 déc 2004 à 02:09 (CET)

Hiérarchie des classes

Il faudrait compléter les relations d'inclusions sur les classes (indiquer celles qui sont prouvées, les inclusions strictes conjecturées, les théorèmes qui indiquent que si une inclusion n'est pas stricte, alors la hiérarchie s'effondre, etc.). David.Monniaux 20 déc 2004 à 09:07 (CET)

c'est quoi NSPACE ? (dans P ⊆ NP et Co-NP ⊆ PSPACE ⊆ NSPACE) généralement on écrit NSPACE(f(n)) et PSPACE par exemple c'est l'union des NSPACE(n^c) pour tout c non nul. Mais je crois que c'est une erreur de frappe plutôt. Par contre c'est démontré que PSPACE = NPSPACE. Et vaut mieux éviter les « ⊆ » vu que ces inclusions (à part la dernière) sont strictes pour l'instant. Pour les inclusions prouvées c'est celles que j'ai mises. Bon il y en a d'autres. La conjecture que je connais c'est P ≠ NP. Pour le reste je ne sais pas trop, je ne me suis pas intéressé aux conjectures. Tom 20 déc 2004 à 10:38 (CET)

Oui, suis-je bête (il suffit de simuler en revenant et en effaçant l'espace). Ce à quoi je faisais allusion, c'est qu'on a des théorèmes du style "si P=NP, alors <truc totalement bizarre arrive, style écroulement de hiérarchies>". David.Monniaux 20 déc 2004 à 10:57 (CET)

Je ne suis pas un expert. Mais de ce qui est démontré pour que ça s'écroule il faudrait l'écroulement du modèle des machines de Turing. De ce que je sais si P=NP ça fait juste qu'on aura de meilleurs algorithmes pour les problèmes NP complets par exemple. Mais sinon je ne vois pas. En physique c'est plus courant d'élaborer des théories sur des conjectures, mais je ne sais pas si c'est fait en informatique et en particulier en complexité. Il faudrait demander à un expert en complexité. Je sais que des gens travaillent sur des algorithmes exponentiels pour trainter les problèmes NP-complets, en essayant de réduire la constante au maximum. Ce genre de travail ne servirait plus à grand chose si P=NP. Tom 20 déc 2004 à 12:03 (CET)

En informatique, le raisonnement habituel est: « machin est un problème NP-complet, donc (moyennant conjecture très solide) non soluble en temps polynômial, donc en pratique non résoluble ». Et, effectivement, une fois qu'un problème est démontré NP-complet, on cherche des algorithmes exponentiels mais efficaces en pratique.

Le point auquel je faisais référence est qu'on a démontré que si P=NP, alors il y a aussi un certain nombre d'égalités entre classes de complexités qui sont vraies. Or, on conjecture également celles-ci comme étant des inclusions strictes. Ça renforce donc la conjecture. Mais je n'ai pas les références en tête (bien qu'informaticien, je ne suis pas expert en théorie de la complexité : une fois que j'ai démontré qu'un truc était NP- ou PSPACE-complet, je considère que c'est une bouse insoluble en général). David.Monniaux 20 déc 2004 à 12:33 (CET)

Il me semble que tu fais une grave erreur en considérant qu'à partir du moment où un problème est NP-Complet, il s'agit d'une "bouse insoluble". La théorie de la complexité repose sur l'étude de la complexité "pire-cas". Pour qu'un problème soit dans NP, il suffit qu'il existe une instance difficile. Il suffit que les instances difficiles soient suffisemment peu nombreuses pour que le problème soit soluble dans la plupart des cas. Pour t'en convaincre, regarde les cryptosystèmes basés sur le Problème du sac à dos qui sont tous cassés successivement.

Algorithme d'approximation/optimisation

Pour attaquer des problèmes NP-complets c'est des algorithmes d'approximation qui sont utilisés, pas des algorithmes d'optimisation. Voir Introduction à l'algorithmique de Cormen, Leiserson, Rivest et Stein chapitres 34 et 35 + Computers and Intractability : A guide to the theory of NP-completeness de Garey et Johnson chapitre 6.

Les algorithmes d'optimisation c'est en programmation linéaire (recherche opérationnelle). Quand à la page algorithmes d'optimisation elle semble faire double emploi avec la page Optimisation (mathématiques) donc problème. Tom 27 déc 2004 à 11:34 (CET)

Attention, les algorithmes d'optimisation couvrent un champ beaucoup plus large que la programmation linéaire ! Il me semble qu'en fait, les "algorithmes d'approximations" (que je connais sous le terme "non exact") sont un sous ensemble des algorithmes d'optimisation.

Pour l'article je pense qu'il faut séparer proprement les méthodes exactes des méthodes approchées. Je propose dans la première catégorie la programmation linéaire, quadratique, dynamique, les méthodes de descente, etc. Dans la seconde, les heuristiques, les métaheuristiques.

Je ne connais que le pendant "optimisation" des problèmes NP-complets, aussi je ne suis pas un bon juge, mais il me semble qu'au moins une grande partie des problèmes NP-complets peuvent se ramener à un problème d'optimisation, non ?

Sinon, il est vrai que l'article algorithmes d'optimisation devrait sans doute être remanier, pour ne laisser apparaitre que la partie algorithmes, et non pas optimisation, qui devrait être mise dans Optimisation (mathématiques).

NoJhan 27 déc 2004 à 20:42 (CET)

d'un point de vue informatique je n'ai pratiquement jamais entendu parler d'algorithmes d'optimisation. D'ailleurs google ne donne pratiquement rien là dessus. Par contre les algorithmes d'approximations sont très utilisés et très étudiés. La référence que j'ai mis au dessus, le Garey et Johnson est le meilleur livre sur l'algorithmique en ce qui concerne les problèmes NP-complets et il y a un chapitre entier sur les algorithmes d'approximation. Par contre je n'ai pas vu d'algorithmes d'optimisation. Ce sont les problèmes qui sont des problèmes d'optimisation. En fait les problèmes NP-complets sont des problèmes de décision mais on transforme un problème d'optimisation en problème de décision en grugeant : "est-ce que la sortie est inférieure à k" par exemple. Il faut distinguer la nature du problème et la méthode de résolution. Tom 27 déc 2004 à 22:49 (CET)

Si saint google le dit :) Il faut raison garder, "algorithme d'optimisation" signifie "algorithme qui résoud un problème d'optimisation". C'est un raccourci, certes, mais je peux dire d'expérience que c'est un terme utilisé dans le domaine où je travaille... Maintenant, c'est vraisemblablement un simple problème de jargon entre le domaine de l'informatique théorique et celui de la recherche opérationnelle.

Je propose de laisser approximation, mais de remanier le paragraphe sur les méthodes, qui mérite une meilleure classification. Je propose également de mettre un petit paragraphe sur le rapport avec les problèmes d'optimisation, avec liens idoines.

NoJhan 28 déc 2004 à 00:16 (CET)

Je proposerais de mettre un lien vers la recherche opérationnelle justement. Parfois ça résoud des problèmes qui ne sont pas NP-complets je pense mais c'est une discipline à part entière et qui je crois est déjà bien wikifié. Un jour j'ai vu quelques articles en coup de vent il me semble. Le fait important ici c'est que c'est distinct des algorithmes d'approximation. Un compromis serait peut être de mettre les deux. Il faudrait faire la page algorithmes d'approximation et modifier la page algorithmes d'optimisation pour faire plus ressortir le côté algorithmique. Tom 28 déc 2004 à 10:52 (CET)

fusion avec complexité algorithmique

Je ne suis pas vraiment d'accord. Je trouve qu'il y a de la place pour les deux articles. Balancer l'article théorie de la compelxite a qqun qui vient timidement se rensigner sur la complexité algorithmique me parait un peu violent. Est il possible de retirer les bandeaux?

Je suis bien d'accord: même si les titres sont proches, les deux articles sont très complémentaires et non redondants. Il faudrait rajouter quelques lignes à la fin de l'article sur la complexité algorithmique pour que le lecteur comprenne qu'elle est à la base de la théorie de la complexité (un peu comme l'addition et la multiplication sont à la base de l'algébre).Francis.sourd

Ayé j'ai enlevé le bandeaux et ai rajouté la petite phrase d'introduction en bas de complexité algorithmique. as4 1 septembre 2005 à 20:42 (CEST)

Discussion transférée depuis PàF

Complexité algorithmique et Théorie de la complexité (bandeaux ôtés le 1 septembre sans fusion)

Je ne suis pas trop sur mais quand on regarde les lines dans les autres langues il semble qu'il s'agit exactement du même sujet mais je ne sais pas quel nom est le plus correct. Pseudomoi 3 jul 2005 à 15:03 (CEST)

Je ne suis pas d'accord sur la fusion. La théorie de la complexité et la complexité algorithmique sont deux choses différentes. Le premier est de la calculabilité pure et donc s'intéressent à des problèmes et analyse la complexité dans un modèle de calcul (généralement les machines de Turing), alors que le second cherche à décrire la complexité d'un algorithme. Le fond est le même mais l'approche est totalement différente. Tom 7 juillet 2005 à 14:00 (CEST)

Tom développe d'excellent argument ... pour la fusion ! Clairement, Théorie de la complexité est actuellement strictement informatique et même algorithmique, son titre doit absolument refléter son contenu. Inversement, le titre Théorie de la complexité doit plutôt renvoyer à complexité, théorie du chaos, etc. gem 11 juillet 2005 à 16:29 (CEST)

La complexité algorithmique permet de comparer des algorithmes entre eux (comme les algos de tri par exemple), la théorie de la complexité compare des problèmes entre eux. Ce n'est donc a priori pas la meme chose et ça n'a pas la meme utilité.--Manproc 26 juin 2006 à 15:59 (CEST)

Fusion avec Classe de complexité P et NP *ET* Classe de complexité

Voilà, j'ai fusionné les 3 articles redondant (ou plutot, inclus les uns dans les autres).

• "Classe de complexité" contenait moins d'information que celui là, je n'ai pas récupéré grand chose ;
• "Classe de complexité P et NP" contenait des discussions sur le sujet que j'ai intégrées dans l'article ;

Dans la foulée, j'ai corrigé quelques détails qui m'apparaissait érroné et j'ai rajouté quelques détails (notamment un petit bout sur les machines à ADN.

Évidemment, c'est sans doute loin d'etre parfait compte tenu du formalisme du domaine, mais je pense ne pas avoir laisser passer de grosses erreurs. En revanche, l'article parait encore assez hermétique au non initié (il faudrait peut-etre se fendre de quelques images de graphes et des patates pour les ensembles...).

--Manproc 26 juin 2006 à 15:58 (CEST)

Temps logarithmique

Si L et LOGSPACE désignent la même chose, comment nomme-t-on la classe des problèmes solvables en temps logarithmique ? - Eusebius ^[causons] 24 janvier 2008 à 09:16 (CET)

Essentiellement on ne la nomme pas: si on prend comme modèle de calcul des machines de Turing, il faut de toute façon un temps linéaire pour déplacer la tête de lecture jusqu'à la dernière lettre de l'entrée. Donc si ton problème peut dépendre de toute l'entrée, tu es en temps linéaire. Je ne crois pas que même avec des machines RAM cette classe soit intéressante. - Galbolle 25 janvier 2008 à 18:12 (CET)

D'accord merci, j'aurais sans doute pu trouver ça tout seul, mais réfléchir c'est tellement fatigant... - Eusebius ^[causons] 26 janvier 2008 à 07:45 (CET)

Je ne sais pas s'il y a des problèmes « intéressants » en temps logarithmique, mais je sais qu'il y a des problèmes de décision, « raisonnablement » intéressant, qui ne nécessitent pas forcément de lire toute la donnée, par exemple il y a des problème de décision qui ne nécessitent de lire que le premier caractère et sont donc en temps constant. Pierre de Lyon (d) 26 janvier 2008 à 10:35 (CET)

Accessoirement, avec une machine de Turing si on n'a pas au moins un temps linéaire pour aller jusqu'à la fin de l'entrée, on ne peut pas connaître sa taille. Du coup on ne peut pas s'arrêter en temps logarithmique. Pour que TIME(f(n)) soit une classe de complexité digne de ce nom, il faut que f soit constructible en temps, ce qui implique qu'elle soit plus grande que l'identité. Un paragraphe là-dessus serait d'ailleurs le bienvenu à l'occasion. Galbolle 28 janvier 2008 à 17:05 (CET)

Je ne comprends pas cet argument. Pourriez-vous être plus explicite. Pierre de Lyon (d) 30 janvier 2008 à 18:14 (CET)

Une fonction f est constructible en temps s'il existe une machine qui sur toute entrée de taille n s'arrête en temps f(n). Les théorèmes de théorie de la complexité (Savitch, hiérarchie...) s'appliquent en général à des classes de la forme TIME(f(n)) avec f constructible. C'est donc une bonne notion de classe non pathologique. Galbolle 31 janvier 2008 à 13:58 (CET)

Je ne comprends pas plus. Pierre de Lyon (d) 1 février 2008 à 21:10 (CET)

Il y a deux choses. D'abord, une classe TIME(f(n)), avec f(n) = o(n) ne peut contenir que des problèmes en temps constant. Pour s'en convaincre, il suffit de constater que si f(N) < N, alors sur une machine qui fonctionne en temps f(n), sur une entrée de taille N, ne peut pas lire le dernier caractère de l'entrée, ni connaître sa taille. Donc sur une entrée x de taille supérieure, elle se comporte comme sur le préfixe de x taille N. Elle s'arrête donc sur toute entrée en un temps borné par une constante. D'autre part, pour éviter les cas pathologiques comme celui-ci, ou du type TIME(g(n)) avec g complètement artificielle et incalculable, la plupart des théorèmes de complexité commencent par «soit g constructible en temps…». La définition de constructible en temps (en:Constructible function) est qu'il existe vraiment une machine M qui s'arrête en temps g. Je me demande s'il est bon de présenter cette notion dans l'article: elle n'est pas nécessaire à la compréhension intuitive, mais elle intervient réguliérement comme hypothèse dans les théorèmes classiques.Galbolle 1 février 2008 à 22:49 (CET)

Fusion Théorie de la complexité et Complexité algorithmique

La fusion de ces deux pages est nécessaire. D'ailleurs, ces deux pages pointent sur les mêmes interwiki. De plus, aucun de ces deux articles n'est bien nommé. "Théorie de la complexité" est trop général, et désigne bien d'autres choses que le sujet de l'article. "Complexité algorithmique" est un homonyme entre le sujet de l'article, et un type de complexité, n'ayant rien à voir, en théorie algorithmique de l'information (Théorie de la complexité algorithmique mauvais titre également, mais c'est une autre histoire). "Complexité algorithmique" devrait être une page d'homonymie. Je propose Complexité algorithmique (Informatique théorique) comme titre de l'article fusionné. --Jean-Christophe BENOIST (d) 1 juin 2009 à 14:13 (CEST)

Les parenthèses de désambiguïsation devrait être évités autant que possible. Est-ce que le type de complexité qui porte ce nom a vraiment vocation à devenir un article ? Si on peut juste le développer en tant que section d'article et éviter les parenthèses cela serait mieux. Je ne suis pas un spécialiste mais ce me parait suffisamment précis pour éviter une page d'homonymie. Outs (d) 1 juin 2009 à 15:05 (CEST)

Complexité des algorithmes pour la fusion "théorie de la complexité" et "complexité algorithmique" et Théorie de l'information algorithmique pour "Théorie de la complexité algorithmique" ? Léna (d) 1 juin 2009 à 16:13 (CEST)

Complexité des algorithmes : oui, pourquoi pas, mais je préfère la proposistion parenthèsée. "Complexité algorithmique" est plus connu et consacré que "Complexité des algorithmes" (qui est utilisé aussi, mais moins).

Théorie de l'information algorithmique : non, ce n'est pas un terme consacré (Google test pratiquement nul), et va bien au delà du sujet originel de l'article qui est sur la complexité. Pour moi, le nouveau nom de Théorie de la complexité algorithmique devrait être Complexité (Théorie algorithmique de l'information) (désolé pour les parenthèses ). En revanche, il faudrait un article sur la Théorie algorithmique de l'information - ce qui n'est pas du tout pareil que Théorie de l'information algorithmique.

D'habitude, je suis bien en phase avec les règles de WP, mais je trouve que vouloir éviter les parenthèses à tout prix, c'est excessif, surtout s'il faut se contraindre à des choses pas naturelles pour cela (acrobaties de titre, prise d'un titre moins connu, ou faire des sections dans un article etc..). Il s'agit bel et bien là d'homonymes, de termes consacrés dans leur domaine, mais dans plusieurs domaines différents : donc tout à fait le cas de figure des titres parenthèsés. --Jean-Christophe BENOIST (d) 1 juin 2009 à 18:47 (CEST)

Ce n'est pas interdit, si c'est justifié il n'y a pas de problème. Outs (d) 2 juin 2009 à 10:46 (CEST)

A ma connaissance la théorie de la complexité est une discipline bien précise en informatique théorique. Peut-être est-il nécessaire de préciser le contexte dans le titre ?--Silex6 (d) 3 juin 2009 à 21:56 (CEST)

Oui c'est vrai, c'est d'ailleurs aussi un titre possible pour l'article fusionné. Nous sommes donc avec trois possibilités Complexité (Informatique théorique), Complexité des algorithmes, ou Théorie de la complexité (Informatique théorique). Bon, on peut toujours faire la fusion, et se décider pour le titre en dernier. --Jean-Christophe BENOIST (d) 4 juin 2009 à 21:12 (CEST)

Pitié, ne gardons pas la Théorie de la complexité des algorithmes! C'est lourd et artificiel au possible. Si on ne veut pas de parenthèses, Complexité des algorithmes me semble être le meilleur titre, d'autant plus que « théorie de » est toujours redondant en maths, non? Galbolle 13 juin 2009 à 13:27 (CEST)

J'ai effectué un essai de fusion entre les deux articles. J'ai décidé de laisser tomber certaines informations de Complexité algorithmique qui étaient déjà présentes dans l'autre article, sous une autre forme (plus formelle et plus précise, mais peut être moins accessible). Des avis sur le résultat ? --Jean-Christophe BENOIST (d) 4 juin 2009 à 21:35 (CEST)

Amusant : voir la demande de fusion (cf ci-dessus) de 2005 refusée. Comme quoi, tout évolue ... Jerome66 12 juin 2009 à 08:55 (CEST)

Pourquoi pas, mais la partie classes de complexité tombe un peu comme un cheveu sur la soupe: elle est beaucoup plus technique que le reste (c'est normal, les deux articles fusionnés n'avaient pas le même ton). Je serais assez tenté d'évoquer rapidement les principales classes (P, NP et PSPACE) dans le corps de l'article, et renvoyer pour plus de détails à un « Classe de complexité » dé-redirecté. Ça éviterait d'avoir tout le complexity zoo dans l'article introductif, même si on en est encore loin. En l'état, je pense que c'est un meilleur article « Théorie de la complexité » que ce qu'on avait, mais un moins bon « Complexité Algorithmique », car les approches utilisées par les véritables algorithmiciens sont reléguées à la portion congrue, d'où ma suggestion pour rééquilibrer Galbolle 12 juin 2009 à 14:05 (CEST)

La partie "Classe de complexité" était déjà là et ne vient pas de la fusion. Rien n'a changé à ce niveau. Les seules parties qui viennent de la fusion sont l'historique et le tableau des complexités en grand O. Pour le moment, l'article ne semble pas encore suffisamment volumineux pour envisager une scission, surtout juste après une fusion , et surtout le titre "Théorie de la complexité" réfère en premier lieu à l'étude des classes de complexité, qu'il ne faudrait du coup en aucun cas déporter dans un autre article !

Oui, je prenais le point de vue de complexité algorithmique. Quelqu'un qui cherche la page complexité algorithmique peut avoir du mal à retrouver ses petits dans ce qu'il va trouver. Fais l'expérience, pars de Algorithme, va à la section Complexité algorithmique, et suis le lien Complexité algorithmique. Tu vois le problème? La fusion marche bien du point de vue théorie de la complexité, moins bien du point de vue complexité algorithmique.

D'ailleurs, et pour preuve, l'article classe de complexité que tu proposes auraient les mêmes interwikis que cet article, ce qui ne va pas.

Absolument pas, du moins pas en anglais, espagnol ni allemand (ni italien pour autant que je puisse en juger).

En fait, ce que tu proposes, à un mic-mac de titres près, est de revenir à la situation antérieure à la fusion avec un article orienté "Théorie de la complexité" (ou "classes de complexité") et un article plus orienté vers la complexité algorithmique, notation grand O etc.. Pourquoi pas ! Il y a du pour et du contre à la fusion (plus de "pour" AMO) et j'ai laissé du temps à tout le monde pour s'exprimer avant de réaliser la fusion. Mais il n'est pas trop tard pour discuter, même si c'est un peu dommage que cela n'aie pas eu lieu avant.

C'est vrai, à ceci près qu'on aura un pont naturel de complexité algorithmique vers théorie de la complexité. Mon principal souci, c'est de concilier les deux objectifs suivants: complexité algorithmique renvoie vers un endroit avec une explication simple de la complexité d'un algorithme, et classe de complexité renvoie vers quelque chose de complet. Après, mettre l'introduction à théorie de la complexité dans le même article que complexité algorithmique, je te fais confiance, à condition que l'article reste équilibré.

Pour le moment, cela n'urge pas de scissionner : pourquoi ne pas travailler les deux aspects dans cet article, et SI et QUAND l'article sera suffisament bien structuré et volumineux pour découper, on pourra rediscuter d'un scission, avec plaisir . En tout cas merci pour tes remarques (je me sentais bien seul jusqu'ici). Cordialement --Jean-Christophe BENOIST (d) 13 juin 2009 à 01:17 (CEST)

À mon avis, ce serait pas mal de faire la scission maintenant, parce que ça permettrait d'équilibrer l'article et donc les contributions sans attendre. Mais c'est une question de méthodologie, je préfère avoir une ébauche avec un bon plan qu'un fouillis fourni. Galbolle

Une petite remarque de forme tout d'abord, pas bien grave d'autant que tu sembles nouveau sur Wikipédia et que tu ne connais pas encore toutes nos "us et coutumes" : cela "ne se fait pas" de répondre dans le texte d'un autre, même si c'est bien pratique; l'usage veut que on reprenne les phrases de l'autre en italique, par exemple, pour répondre à des points précis. Et n'oublies pas de signer avec --~~~~. Mais encore une fois : pas de problèmes !

Sur le fond, nous sommes clairement sur deux positions différentes. Je ne suis pas viscéralement opposé à une (re)scission à terme, mais plus clairement opposé à une scission immédiate. C'est trop tôt : il n'y a pas de vision claire de l'état final. On risque de se retrouver (de nouveau) avec deux articles redondants, aux contours mal définis, et aux titres peu clairs. Rien n'empêche de travailler les deux aspects dans l'article actuel et d'avoir un plan clair, sur les deux aspects, dans un article unique. Une fois le plan clairement établi dans cet article, où on pourra évaluer les contours des (éventuels) deux futurs articles, alors on pourra procéder (éventuellement ) à une scission.

D'autre part, je ne vois pas, sur WP:en, les deux articles correspondant aux deux aspects. Avant, Complexité algorithmique et Théorie de la complexité pointaient tout deux vers en:Computational_complexity_theory (et c'est un des éléments qui m'a convaincu de faire la fusion). Hors, tu sembles avoir trouvé deux articles sur WP:en, puisque tu dis que ce n'est pas le cas en anglais. Peux-tu nous donner les deux liens sur Wp:en ?, ce serait très intéressant pour la suite de la discussion. Idem sur WP:de, d'ailleurs, où les deux articles pointaient aussi vers un seul et unique article sur Wp:de. Cordialement --Jean-Christophe BENOIST (d) 13 juin 2009 à 13:53 (CEST)

Je ne suis pas si nouveau que ça, mon compte date de 2005, mais je n'ai pas contribué depuis un moment. Il me semble qu'en ces temps préhistoriques, les mœurs n'étaient pas les mêmes… Ok pour commencer à travailler dans un article unique. En fait, en anglais, il y a même trois articles: en:Computational_complexity_theory, en:Analysis_of_algorithms et en:Complexity_class. En allemand, de:Komplexitätstheorie et de:Komplexitätsklasse. Note qu'à chaque fois, l'article « classe de complexité » est plus spécialisé, il s'agit moins d'une scission que d'un Article détaillé pour éviter de balancer des détails abscons (et il y en a pas mal en complexité) dans l'article d'introduction. Galbolle 13 juin 2009 à 14:40 (CEST)

en:Analysis_of_algorithms est intéressant, et je ne suis pas DU TOUT opposé à voir un article français sur le même sujet, même dès maintenant. Mais ce n'est pas un article centré sur la complexité algorithmique, il est beaucoup plus général et la complexité algorithmique en est une petite partie. Je pense qu'il y a une possibilité de quiproquo ou d'incompréhension entre nous étant donné la réponse que tu viens de me faire. La division de:Komplexitätstheorie et de:Komplexitätsklasse, ou en:Computational_complexity_theory et en:Complexity_class n'est pas celle que j'ai cru comprendre que tu proposais. Une scission de cet article telle que sur WP:en ou WP:de est possible (bien que non encore nécessaire car cet article est encore relativement court) et ne revient pas DU TOUT à la division ancienne. La division ancienne (que je viens de fusionner) était entre un article concernant la théorie de la complexité des algorithmes (classes de complexité, P, NP etc..) et un article focalisant sur complexité algorithmique, la notation grand O dans le domaine de l'informatique etc.. J'ai cru que tu voulais revenir à une telle division. Mais comme tu cites en exemple des divisions qui n'ont pas de rapport avec cela, je m'interroge. En d'autres termes, et en un mot, il n'y a pas de division, sur WP:en ou sur WP:de telle qu'il en existait avant la fusion.

Pour (essayer d') être parfaitement clair : proposes tu une scission telle que de:Komplexitätstheorie et de:Komplexitätsklasse, ou en:Computational_complexity_theory et en:Complexity_class, ou une scission entre un article traitant des classes P, NP etc.. et un autre traitant de la complexité algorithmique (sachant que cette division n'existe pas sur WP:en et WP:de) ? Cordialement --Jean-Christophe BENOIST (d) 13 juin 2009 à 16:23 (CEST)

Oui, je pensais à la même scission qu'en anglais et allemand. Galbolle 13 juin 2009 à 18:42 (CEST)

Alors, nous nous sommes effectivement mal compris. Sur cette scission là, pas de problème, si ce n'est que je trouve l'article pas encore assez long et développé pour la faire, mais rien de fondamental. Mais il reste un point à éclaircir (et qui a mené au quiproquo) : quand tu disais Fais l'expérience, pars de Algorithme, va à la section Complexité algorithmique, et suis le lien Complexité algorithmique. Tu vois le problème : je pense qu'il y aura toujours le même "problème" avec la scission de type en/de, car cette scission ne concerne pas la complexité algorithmique.. --Jean-Christophe BENOIST (d) 13 juin 2009 à 19:15 (CEST)

Bibliographie

Je trouve la bibliographie largement améliorable. Le "Computational Complexity" de Papadimitriou et le Garey-Johnson sont deux incontournables. On pourrait rajouter le très récent "Computational Complexity: A Modern Approach" de Sanjeev Arora et Boaz Barak, qui tend à s'imposer comme une référence (et qui a le bon goût d'être disponible sous forme de Drafts à l'adresse suivante. Pour les références en français, le Lassaigne/de Rougemont est une bonne référence, mais l'"Introduction à la calculabilité" ne me semble pas avoir sa place ici. Enfin, le "Modal Logic" me semble parfaitement inapproprié, et la référence de l'article de Hermann et Lescanne aurait à mon avis plus sa place en note par rapport à la partie "Le problème ouvert P=NP" qu'en référence générale sur le sujet. Cela dit, ce n'est peut-être pas la bonne façon de faire, je ne suis pas très expert wikipédien. Dernière chose, il y a peut-être moyen de trouver une référence en français plus moderne que le Lassaigne/de Rougemont qui commence à sérieusement dater... (même s'il est excellent ;-)).

Je ferai des modifications d'ici peu si personne ne s'y oppose !--Grob (d) 8 novembre 2009 à 17:51 (CET)

Tout cela parait de bon aloi. On t'en prie ! --Jean-Christophe BENOIST (d) 8 novembre 2009 à 19:19 (CET)

Modifications faites. J'ai finalement laissé l'article de Hermann et Lescanne qui peut être intéressant. Au passage, je pense que cette page ne présente qu'une partie de la complexité algorithmique (en fait la complexité booléenne), et qu'on pourrait signaler l'existence de la complexité quantique, la complexité algébrique, etc... Ces domaines étant par exemple présent dans la conférence "Computational Complexity Conference". J'essaierai de réfléchir à une bonne méthode pour en parler dès que j'aurai le temps --Grob (d) 9 novembre 2009 à 00:49 (CET)

Article séparé pour NP-complet

Bonjour,

Je compte créer prochainement une page séparée pour Problème NP-complet, il me semble que c'est une notion assez importante pour faire l'objet d'un article en elle-même (il n'y a qu'à voir quelles sont les pages liées à celle-ci).

J'ai commencé une traduction (libre) de la version anglaise sur Utilisateur:Nordald/Problème NP-complet, mais je vois que certains articles spécifiques sur les classes de complexités ont déjà été fusionnés dans Théorie de la complexité des algorithmes, donc je demande d'abord : avez-vous des commentaires ou des objections sur la création de l'article Problème NP-complet ?

Cordialement, Nordald (d) 14 mai 2010 à 00:38 (CEST)

Notion très importante en effet, qui mérite largement un article. Pour ma part, aucun problème, au contraire. Ce qui avait été fusionné était deux articles, qui se recouvraient beaucoup, et aux contours imprécis. Le destin de cet article est de donner lieu maintenant à des sous-article plus précis, ce qui est le cas pour cet article. Bon courage pour la traduction et pour l'article ! Cordialement --Jean-Christophe BENOIST (d) 14 mai 2010 à 01:45 (CEST)

Je suis aussi favorable à la création d'un article intitulé Problème NP-complet. --Pierre de Lyon (d) 14 mai 2010 à 11:17 (CEST)

Merci de vos réponses, je m'occupe donc de développer cet article (pour l'instant, toujours sur ma page utilisateur). Bonne journée, Nordald (d) 14 mai 2010 à 13:55 (CEST).

Voilà, une première version est en ligne dans l'espace principal : Problème NP-complet. Je n'ai suivi la version anglaise que partiellement. N'hésitez pas à me faire part de vos remarques et critiques et/ou à modifier l'article. Il y a maintenant une certaine redondance entre cet article et celui-ci, qu'il faudra sans doute retravailler un peu. Nordald (d) 15 mai 2010 à 22:39 (CEST)

A première vue, c'est du très bon travail. Toutes mes félicitations et mes encouragements. Je regarderais de manière plus attentive plus tard. Cordialement --Jean-Christophe BENOIST (d) 16 mai 2010 à 10:28 (CEST)

Histoire

Comment on invente des histoires

Dans les années 1960 et au début des années 1970, alors qu'on en était à découvrir des algorithmes fondamentaux (tris tels que quicksort, arbres couvrants tels que les algorithmes de Kruskal ou de Prim), on ne mesurait pas leur efficacité. On se contentait de dire : « cet algorithme (de tri) se déroule en 6 secondes avec un tableau de 50 000 entiers choisis au hasard en entrée, sur un ordinateur IBM 360/91. Le langage de programmation PL/I a été utilisé avec les optimisations standards. » (cet exemple est imaginaire)

A mon avis c'est un peu n'importe quoi, puisque von Neumann donne dans son First Draft of a Report on the EDVAC un algorithme de tri en O(n log n). Il avait donc bien conscience de la complexité des algorithmes.--Pierre de Lyon (d) 31 décembre 2010 à 11:39 (CET)

Oui. Je pense que les créateurs des algorithmes (von Neumann, Knuth etc..) ne pouvaient qu'avoir conscience au moins d'une certaine forme de complexité des algorithmes (sinon, comment formaliser leur efficacité et comparer différents algorithmes ?). Tout dépend de qui désigne le "on", qui semble désigner tour à tour créateurs et utilisateurs. Je pense que l'idée générale de la phrase est de dire quelque-chose comme : "à cette époque la notion de complexité n'était pas très formalisée, et réservée aux créateurs des algorithmes, qui avaient chacun leur notion de la chose". Mais est-ce vrai ? Je n'ai pas de source sur cet historique. --Jean-Christophe BENOIST (d) 31 décembre 2010 à 12:00 (CET)

A mon avis c'est de la pseudo histoire. Je supprime donc cette affirmation non pas parce qu'elle n'est pas étayée, mais parce qu'elle est fausse. --Pierre de Lyon (d) 4 janvier 2011 à 16:57 (CET)

Je viens de lire l'article de Knuth "The Dangers of Computer Science Theory" où il trace l'origine de l'analyse des algorithmes de tri à la thèse de Demuth en 1954. Comme les premiers algorithmes datent des Babyloniens, au début du deuxième millénaire avant JC, il est difficile de dater précisément le début de l'analyse des algorithmes, je pense qu'il faut donc rester vague sur la date. Puis-je enlever la première demande de date ? --Pierre de Lyon (d) 5 janvier 2011 à 12:07 (CET)

Ceci écrit, j'ai ajouté les références à Demuth et à Knuth qui donnent donc des dates précises pour la deuxième demande de date.--Pierre de Lyon (d) 5 janvier 2011 à 15:16 (CET)

J'en profite aussi pour relever une erreur classique qui consiste à confondre l'origine de l'algorithmique avec celle de la calculabilité et de l'informatique. Les scientifiques concevaient des algorithmes bien avant Turing et Ecker et Maulchy. --Pierre de Lyon (d) 5 janvier 2011 à 15:29 (CET)

J'ai retiré ma première demande de date mise essentiellement car avant ton intervention une date était donnée et j'ai cru à une omission. Sinon l'algorithmique c'est bien sûr plus ancien que la calculabilité, penser aux recettes en tout genre (cuisine) ou à l'algo d'Euclide (même s'il n'est p.-e. pas de lui) ou technique du boulier, pour rester en maths pour exemple. --Epsilon0 ε₀ 5 janvier 2011 à 19:02 (CET)

Knuth et la théorie de l'information

Encore moi. J'ai lu les articles historiques de Knuth (il se trouve que ça tombe pile avec les besoins d'un article que j'écris). Je note qu'il ne parle pas de la théorie de l'information comme fondement de l'analyse d'algorithme. J'ai l'impression que l'article lui prête des pensées qu'il n'a pas. --Pierre de Lyon (d) 5 janvier 2011 à 21:00 (CET)

La démonstration de la complexité minimale du tri en n Log(n) à partir de l'entropie est connue (par exemple p.3 de [1]). Mais je ne sais pas si c'est Knuth qui en est à l'origine. C'est possible. --Jean-Christophe BENOIST (d) 5 janvier 2011 à 21:45 (CET)

L'intermédiaire mathématique de 1894

Knuth signale une analyse d'algorithme de 1894 parue dans l'Intermédiaire mathématique de 1894. Quelqu'un saurait-il si cet ouvrage est disponible en ligne? --Pierre de Lyon (d) 5 janvier 2011 à 21:06 (CET)

Découpage en plusieurs pages, nom des pages

Ce sujet a déjà été maintes fois débattu sur cette page, et je suis donc désolé de remettre le couvert. Cependant, je trouve que l'article actuel est un peu "brouillon" car on y parle un peu de tout et n'importe quoi à la fois. Je vais essayer de m'expliquer. En gros, mon avis sur la question serait de suivre la version anglophone.

Il ne faut pas confondre deux domaines de l'informatique théorique distincts qui sont l' analyse des algorithmes d'une part, et l'étude de la complexité structurelle d'autre part (pour les noms, voir un peu plus bas). Le premier domaine consiste à prendre un algorithme ou une famille d'algorithmes et d'en étudier le temps de fonctionnement par exemple (ou l'espace utilisé). On peut étudier le temps dans le pire cas, en moyenne, en analyse amortie, etc... Pour citer des "papes" du domaine, on peut citer Donald Knuth ou encore le regretté Philippe Flajolet. Le deuxième domaine consiste à étudier les classes de complexité en tant que telles. Si l'objet d'étude dans le premier cas est l'algorithme, dans le deuxième il s'agit plutôt d'étudier le modèle de calcul. D'ailleurs, dans ce domaine, on fait varier le modèle de calcul pour comparer les puissances de calcul obtenus (machine de Turing déterministe, non déterministe, probabiliste, circuit booléen uniforme ou non, modèle de calcul quantique, etc...). C'est le domaine qui pose la question de P versus NP par exemple. On peut bien sûr établir des liens entre les deux domaines, mais ils sont bien distincts. D'ailleurs, les bouquins traitent en général l'un ou l'autre des domaines et pas les deux. De la même façon, les chercheurs des deux domaines ne publient pas vraiment dans les même conférences ou journaux, à part quand il s'agit de conférences ou journaux très généralistes (comme Theoretical Computer Science).

Ce que je propose du coup est de créer une page Analyse de la complexité des algorithmes, et une autre sur la Théorie de la complexité. La page Classes de complexité peut aussi avoir son intérêt mais elle n'est à mon sens pas au même niveau que les deux autres : c'est une "sous-page" spécialisée de Théorie de la complexité.

Pour ce qui est des noms, je pense que la page Analyse de la complexité des algorithmes ne prête pas trop à confusion. Par contre, c'est pour l'autre page qu'on est embêtés (et ça depuis longtemps étant donné les discussions à ce sujet qui remontent à... 2005 !). En fait le problème vien "tout simplement" du fait que ce domaine porte en anglais le nom de "Computational Complexity Theory" et que ce nom n'a pas de bonne traduction en français. Les gens du domane parlent de "Théorie de la complexité" ou de "Theorie de la complexité algorithmique" mais comme il a été dit, cela porte à confusion hors du domaine, donc dnas une encyclopédie. Je n'ai pas encore de bonne idée pour l'appellation. Ce que je propose de manière pratique est que cette page serve à la "Théorie de la complexité" et qu'une nouvelle page soit créée pour "Analyse des algorithmes". De manière pragmatique, le plus simple est sans doute de créer cette nouvelle page sans changer celle-ci, et qu'une fois que la nouvelle page est écrite et stabilisée, on enlève un peu de celle-là ce qui fait doublon, puis qu'on la complète (avec la complexité quantique, etc...).

Qu'en pensez-vous ? Grob (d) 20 avril 2011 à 01:38 (CEST)

Je suis d'accord qu'il est nécessaire de rediscuter du découpage et du périmètre de cet article. Tu dis qu'il faudrait s'inspirer de WP:en (ce en quoi je suis tout à fait d'accord), mais à quel article WP:en correspondrait Analyse de la complexité des algorithmes : en:Analysis of algorithms ? C'est juste pour avoir les idées claires.

Oui tout à fait, c'est de cette page que je parlais.

Sur le nom de cet article, tu n'as pas dit en quoi Théorie de la complexité des algorithmes ne convient pas. J'avais renommé l'article ainsi naguère, pour éviter la confusion avec d'autres théories traitant de la complexité, et c'est une traduction de "Computational Complexity Theory" utilisée régulièrement par Jean-Paul Delahaye dans ses articles et ouvrages. "Théorie de la complexité algorithmique" est aussi utilisée pour désigner ce domaine, c'est vrai, mais il y a malheureusement une confusion possible avec un domaine de la théorie algorithmique de l'information, la "complexité algorithmique" étant un nom souvent donné à la complexité de Kolmogorov. Mais j'ai l'impression qu'il n'y a pas de solution idéale, et que si on s'accorde pour dire que "théorie de la complexité des algorithmes" est trop peu usité, il faudrait renommer cette page, mais "théorie de la complexité" (le titre originel de l'article avant son renommage !) me parait le plus mauvais choix étant donné les multiples "théories de la complexité" qui existent, en passant par celle d'Edgar Morin ! Ou alors faire une page d'homonymie "Théorie de la complexité" avec cet article nommé "Théorie de la complexité (algorithmie)" ?

A l'époque, je n'avais pas eu beaucoup d'interlocuteurs pour parler de tout cela, et je suis content de voir que ce sujet suscite de nouveau de l'intérêt. Cordialement --Jean-Christophe BENOIST (d) 20 avril 2011 à 09:31 (CEST)

Mon problème avec ce nom est le suivant : quand on parle de "Théorie de la complexité des algorithmes", on met l'accent sur "algorithmes" alors que comme je le disais précédemment, l'objet d'étude dans ce domaine n'est pas vraiment l'algorithme, mais plutôt le modèle de calcul. Autrement dit, ce domaine a pour but d'étudier des "problèmes" de nature algorithmique, et non des "algorithmes". Ou pour paraphraser Bruno Poizat (dans Les Petits Cailloux), on étudie l'algorithmique (ou "algorithmie" comme il dit) et non les algorithmes. C'est à mon sens ce qui pousse les gens à parler d'analyse de la complexité des algorithmes dans cette page. "Théorie de la complexité des algorithmes" fait à mon sens pensé qu'on va étudier la complexité de certains algorithmes alors qu'on parle plutôt de l'objet abstrait "algorithme" et pas d'algorithmes spécifiques.

Maintenant pour trouver un nom correct... c'est pas facile ! Effectivement, Théorie de la complexité ne va pas, et au passage je suis d'accord sur le principe d'une page d'homonymie portant ce nom (quelque soit le nom qu'on donne à la page dont on parle ici) puisque des gens peuvent chercher "Théorie de la complexité" sans savoir que ça peut parler de plein de choses différentes. Personnellement, ma préférence va à "Théorie de la complexité algorithmique", et je pense que le problème de confusion avec la "Théorie algorithmique de l'information" peut être réglée par des bandeaux appropriés en début d'articles. Surtout qu'on parle d'un côté de "complexité" et de l'autre d'"information" donc ça sépare relativement bien les domaines. Une autre possibilité qui est plus rarement rencontrée mais peut-être plus fidèle au nom en anglais est Théorie de la complexité du calcul, mais ce n'est peut-être pas très heureux comme formulation. Enfin, ta proposition de Théorie de la complexité (algorithmie) me convient. Je note simplement que dans les discussions précédentes, certains voulaient éviter les parenthèses... Pour tous les noms proposés, enlever le "Théorie de" en début de nom peut alléger, sans que le titre devienne moins clair.

Une petite note : actuellement, Théorie de la complexité algorithmique redirige vers Théorie algorithmique de l'information ce qui me semble une bien mauvaise chose, pour deux raisons. Déjà, il me semble rare qu'on parle de "Complexité algorithmique" pour "Complexité de Kolmogorov" (ou tout autre appellation équivalente) , et d'autre part on utilise souvent ce terme pour "Computational Complexity". Peut-être qu'il faudrait rediriger cette page vers Complexité algorithmique, ce qui serait plus logique.

Cordialement, Grob (d) 21 avril 2011 à 15:56 (CEST)

C'est une discussion intéressante. D'abord, je pense qu'il est nécessaire de refaire une "opération sources", pour rebalayer les terminologies française en vigueur. Une source qui me parait assez représentative est [2] où "complexité algorithmique" et "complexité des algorithmes" est utilisé assez indifféremment. En revanche, cette source sépare nettement "complexité algorithmique (ou des algorithmes)" ( O(n) O(n²) etc.. ) et "complexité des problèmes" (P, NP etc..).

Je suis d'accord avec toi que "théorie de la complexité des algorithmes" porte trop l'attention sur les algorithmes, mais on pourrait presque en dire autant de "complexité algorithmique". Est-ce qu'il ne faudrait pas aller jusqu'au bout de la logique, et nommer cet article comme dans la source que je viens de citer (et d'autres comme [3] ou [4]) Complexité des problèmes, si le sujet de cet article est bien (mais nous sommes d'accord je crois) : P, NP etc.. et leur rapports.

Donc, un autre article serait consacré à la complexité algorithmique/des algorithmes. Je ne pense pas qu'il serait l'équivalent de en:Analysis of algorithms mais plus de en:Time complexity, car il parait nécessaire de parler dans cet article de la hiérarchie des complexités des algorithmes (logarithmique, polynomial, sub-exponentiel, exponentiel etc..) qui n'est pas vraiment décrite dans en:Analysis of algorithms.

Mais je continue de balayer les sources. Codialement --Jean-Christophe BENOIST (d) 21 avril 2011 à 17:04 (CEST)

PS : en effet, je suis d'accord laisser tomber la confusion possible complexité algorithmique/complexité de Kolmogorov. Elle peut exister, mais elle est effectivement mineure. --Jean-Christophe BENOIST (d) 21 avril 2011 à 17:06 (CEST)

Je mets un peu de temps à répondre car je n'avais pas trop de temps ces derniers jours. J'avais pas fait gaffe à en:Time complexity mais tu as raison, cet article correspond mieux à ce dont je parlais. Sinon, pour Complexité des problèmes, ça me gêne un peu parce que c'est trop général en un sens. On parle bien de "complexité algorithmique" dans le sens où c'est la complexité de résoudre un problème par un algorithme. Un entre-deux (lourdingue ?) serait Complexité algorithmique des problèmes.

Je suis d'accord sur le fait de balayer le plus de sources francophones possible. Je n'ai pas encore eu trop le temps de le faire mais vais essayer de m'y atteler. Pour être honnête cependant, je n'ai jamais vraiment trouvé de présentation qui me convenait entièrement, en français, de ce domaine. Mais ça existe peut-être ! Amicalement Grob (d) 8 mai 2011 à 01:01 (CEST)

C'est vrai que c'est pas évident parcequ'en français on parle souvent de Théorie de la complexité tout cour. Théorie de la complexité des problèmes me parait déja mieux adapté, mais il faudrait au moins dire dans l'intro: Théorie de la complexité des problèmes (souvent désigné par théorie de la complexité) ou un truc du genre. --Pparent (d) 21 juin 2012 à 10:03 (CEST)

Oui, je suis d'accord. D'ailleurs, dans l'intro de la source [2] plus haut, "théorie de la complexité" tout court désigne la théorie de la complexité des problèmes. Même si le titre "Théorie de la complexité des problèmes" n'est pas idéal (mais je pense qu'il doit en être proche), il faut aller de l'avant, on pourra toujours renommer (éventuellement) plus tard. --Jean-Christophe BENOIST (d) 21 juin 2012 à 11:07 (CEST)

bah si personne le fait, je finirai par le faire quand j'aurai le temps. Je sais pas encore trop comment renommer un article non-plus. --Pparent (d) 21 juin 2012 à 16:44 (CEST)

Mais oui ! N'hésites pas ! C'est comme cela que les choses avancent. Même si ce n'est pas parfait (mais je t'ai déjà vu travailler, j'ai confiance) cela pousse à réagir et à améliorer. Le "renommer" est bien caché entre l'étoile de suivi et la zone de recherche (petit triangle amenant un menu déroulant). Cordialement --Jean-Christophe BENOIST (d) 21 juin 2012 à 17:57 (CEST)

Confusion complexité Algorithme/problème

Bonjour,

Je trouve que cet article, n'est pas très clair, et mélange complexité des algorithmes et des problèmes.

En général lorsque l'on parle de "théorie de la complexité", il s'agit d'étudier la complexité des problèmes. Et le terme "complexité des algorithmes" est plus ou moins un abus de langage je crois. Wiki en utilise plutot "analysis of algorithms"

wiki (en): A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem.

Donc déja je pense que la première chose à faire et de changer le titre et l'intro. Qu'en pensez-vous? --Pparent (d) 20 juin 2012 à 12:03 (CEST)

ps: désolé je viens de voir la discussion d'au dessus, mais rien n'a été fait depuis.

Je pense qu'il y a consensus sur ce qu'il convient de faire. Il n'y a "plus qu'à". Le premier qui n'hésite pas aura raison ! --Jean-Christophe BENOIST (d) 20 juin 2012 à 12:26 (CEST)

Classes exponentielles

Je trouve que l'utilisation du "grand O" est assez étrange sur cette page. "O(f(n))" est introduit comme une notation pour une certaine classe de complexité. Si je ne m'abuse, il s'agit en fait d'une notation pour un ensemble E de fonctions en n, et la classe de complexité en temps associé est l'ensemble des problèmes tel qu'il existe un algorithme qui résout ce problème et une fonction dans E qui borne le temps d'exécution de l'algorithme. Bref, le problème apparaît surtout pour les classes exponentielles où la "notation" pour la classe ne correspond plus aux fonctions associées: - EXPTIME : résolution en temps $2^{poly(n)}$ n'a rien à voir avec $O(e^n)$ - E : résolution en temps $2^{O(n)}$ n'a rien à voir non plus avec $O(e^n)$ - (de mes souvenirs) SUBEXP : en temps sous exponentiel = $TIME(2^{poly(log(n))})$ n'a rien à voir avec $O(n^{log(n)})$ - je ne sais pas vraiment s'il y a une classe correspondant à la complexité factorielle. En tout cas, si cette classe était $TIME(O(n!))$, ce serait un peu étrange vu qu'alors un problème de complexité $(n+1)!$ ne serait pas factoriel! - je ne connais pas non plus la classe doublement exponentielle, mais je pense que $TIME(2^{2^{poly(n)}})$ serait plus correcte.

Je vais faire les modifications correspondantes, mais je ne sais pas si les deux dernières classes doivent vraiment exister... --Nietsabes 9 septembre 2012 à 16:28

Scission

Bonjour,

J'ai effectué le travail préparatoire à la scission discutée plus haut. Voici les deux articles:

• Théorie de la complexité (informatique théorique)
• Analyse de la complexité des algorithmes

S'il n'y a pas d'objections, j'effectuerai cette scission d'içi a quelques jours. Les articles pourront alors continuer à être améliorés normalement de manière indépendante. Vous pouvez bien sur corriger les éventuelles erreurs sur mes pages de brouillon.

--Pparent (d) 15 octobre 2012 à 17:27 (CEST)

Je n'ai pas d'obection sur la scission, par contre il faudra peut être discuter du nommage des article. Pour moi le premier pourrait s'appeler Théorie de la complexité (algorithmique) parce que Théorie de la complexité est une homonymie, bien qu'il faudrait vérifier pour la complexité de Kolmogorov si elle est bien désignée sous ce nom, et le deuxième complexité algorithmique tout simplement ... Voir « "Théorie de la complexité des problèmes" » (sur Google) n’est de fait pas très employée, voir carrément marginale comme terminologie, même si plus rigoureuse et plus précise dans l'absolu. — TomT0m ^[bla] 15 octobre 2012 à 17:40 (CEST)

Oui le terme employé est "théorie de la complexité" tout court et en pratique il n'y a pas d'autre terme réellement utilisé. Car à moins que l'on précise qu'on parle de la complexité de Kolmogorov, en général on fait référence à celle-ci. Il avait également été proposé "Théorie de la complexité des problèmes", qui semble un poil plus utilisé et plus simple, donc peut-être mieux. --Pparent (d) 15 octobre 2012 à 17:46 (CEST)

Donc, si je résume :

1) la partie "complexité" => A Théorie de la complexité (algorithmique) ou B Théorie de la complexité (algorithmie) ou C Théorie de la complexité des problèmes

2) la partie "algorithme" => Complexité algorithmique

Je serais assez pour 1B et 2. Comme je l'ai dit plus haut, je ne suis pas contre mettre Kolmogorov hors course. --Jean-Christophe BENOIST (d) 15 octobre 2012 à 17:57 (CEST)

Je suis plus pour la 1c car la complexité de kolmogorov n'est pas moins algorithmique (et qu'elle est tout de même importante), et en plus mettre problème dans le titre ça enlève tout de suite l’ambiguïté (qui a mené à son état actuel l'article) que l'on ne s'intéresse pas à la complexité d'un algorithme mais bien d'un problème. La numéro 2 "Complexité des algorithmes" à la limite.--Pparent (d) 15 octobre 2012 à 18:58 (CEST).--Pparent (d) 15 octobre 2012 à 18:58 (CEST)

Je suis pas trop pour ce titre parce que son usage est anecdotique, ça ne correspond pas trop au principe de moindre surprise (cf. Wikipedia:Conventions sur les titres). Dans tous les cas dans les articles il faudrait renvoyer vers les homonymies correspondantes. Tu as des sources pour le nommage "complexité algorithmique" de la complexité de Kolmogorov ? — TomT0m ^[bla] 15 octobre 2012 à 19:48 (CEST)

Non je n'ai pas de sources, mais je n'ai jamais édité cet article, donc il faudrait demander là-bas. Que diriez vous de quelque chose comme "Théorie de la Complexité (problèmes algorithmiques)". La parenthèse n’apparaîtrait que dans le nommage de la page mais pas dans l'intro. --Pparent (d) 15 octobre 2012 à 20:01 (CEST)

Ça m’a l’air beaucoup trop compliqué et inhabituel sur wp, c’est encore plus éloigné du principe de moindre surprise. La convention est de mettre entre parenthèse un domaine, comme les mathématiques ou l’algorithmi(qu)e, pas le domaine des problèmes algorithmiques qui est pour le moins bricolé . La subtilité sur les problèmes doit être expliquée dans l’article. — TomT0m ^[bla] 15 octobre 2012 à 20:15 (CEST)

Oui sauf que dans ce cas particulier on ne peut pas préciser le simple domaine puisque 2 théorie de la complexité font partie de ce domaine, et la deuxième selon l'article se fait également appeler "Théorie de la complexité algorithmique" ce titre redirige même vers la page. Je crois pas que l'on puisse s'en sortir sans faire un truc qui sort un peu de l'ordinaire. Et avoir une page "Théorie de la complexité algorithmique" et "Théorie de la complexité (algorithmique)" qui retournent vers 2 choses complètement différentes avouez que ce serait pour le moins confus.--Pparent (d) 15 octobre 2012 à 20:41 (CEST)

Sur algorithmie vs. algorithmique, j’ai l’impression d’avoir entendu beaucoup plus fréquemment algorithmique, et algorithmie redirige vers algorithmique, donc j’aurai tendance à privilégier la cohérence. Sans plus argumenter ni être formellement opposé à algorithmie. — TomT0m ^[bla] 15 octobre 2012 à 20:15 (CEST)

---

Tant que nous y sommes, un petit récapitulatif de l’existant :

• Complexité algorithmique et Théorie de la complexité en homonymie, actuellement redondant il me semble;
• complexité de Kolmogorov qui est une notion connexe mais très différente;
• complexité des algorithmes qui est une redirection;
• l’article général interdisciplinaire Complexité qui présente différentes notions de complexité dont celles qui nous intéressent;

(j’en oublie sûrement, n’hésitez pas à compléter la liste) Remarque au passage : l’article sur le sujet en anglais est un adq ... il y a surement de quoi s’inspirer dedans (voire de traduire sauvagement ). — TomT0m ^[bla] 15 octobre 2012 à 19:00 (CEST)

Je dois avouer que j'ai un peu perdu le fil de ce qui est proposé en terme de nommage. Je reste pour le moment sur le 1B (ou 1A)/2. En ce qui concerne la complexité de Kolmogorov, Delahaye la mentionne très volontiers en tant que "complexité algorithmique" (par exemple, l'entrée dans l'index du livre Information, Complexité et Hasard de "complexité algorithmique" redirige vers la complexité de Kolmogorov). Cependant, je pense qu'il n'y a guère que Delahaye pour le faire, et encore pas toujours de manière consistante. Donc, même si c'est moi qui suis à l'origine de la page d'homonymie (j'ai été nourri au Delahaye), je pense que cela apporte plus de confusion qu'autre chose, et cela complique (inutilement) la discussion sur le nommage de ces deux articles. Cordialement --Jean-Christophe BENOIST (d) 15 octobre 2012 à 21:21 (CEST)

Donc tu es pour "Théorie de la complexité (algorithmique)". Mais souhaite tu laisser la redirection de "Théorie de la complexité algorithmique" vers la Théorie algorithmique de l'information? Parce que dans ce cas là à 2 parenthèses près on se retrouve sur 2 pages qui non rien a voir, il y a un problème! Je restes sur ma dernière proposition " Théorie de la complexité (problèmes algorithmiques)", qui est certe un peu compliqué mais au moins le sujet de l'article est clair, on peut pas se tromper. --Pparent (d) 15 octobre 2012 à 22:02 (CEST)

Théorie de la complexité algorithmique devrait en fin de compte pointer sur Théorie de la complexité (algorithmique), dans la logique de séparer tout cela de la théorie algorithmique de l'information. Pas trop pour, honnêtement, " Théorie de la complexité (problèmes algorithmiques)". Je pense que ce qui est entre parenthèses doit représenter un vrai domaine dans lequel on pourrait trouver bcp d'articles. Or je pense que cet article, ainsi nommé, sera le seul à avoir ce domaine entre parenthèses. Et pourquoi pas tout simplement Théorie de la complexité (informatique théorique) ? --Jean-Christophe BENOIST (d) 15 octobre 2012 à 22:23 (CEST)

Oui c'est pas mal Théorie de la complexité (informatique théorique), en attendant de trouver mieux. --Pparent (d) 15 octobre 2012 à 22:37 (CEST)

La recherche Voir « "Théorie de la complexité algorithmique" kolmogorov » (sur Google) montre que non, Delahaye n’est pas tout seul à nommer les choses de cette manière. D'ailleurs ça doit être pour ça que Voir « "théorie de la complexité des algorithmes" -site:wikipedia.org » (sur Google) est un terme assez courant, dans des cours par exemple. — TomT0m ^[bla] 15 octobre 2012 à 23:02 (CEST)

Je crois que l'on viens de prouver que ce problème de nommage est au moins NP-Difficile! --Pparent (d) 15 octobre 2012 à 23:32 (CEST)

"Théorie de la complexité des algorithmes" convient également (pour la partie P, NP etc..), et Delahaye la nomme effectivement comme cela souvent. Je manque malheureusement de sources en français (à part Delahaye). Franchement, aucun des trois titres Théorie de la complexité (algorithmique), Théorie de la complexité (informatique théorique), ou Théorie de la complexité des algorithmes ne déshonorerait Wikipédia. Je pense que on converge avec les deux derniers. --Jean-Christophe BENOIST (d) 15 octobre 2012 à 23:54 (CEST)

Pour moi le dernier qui est l'actuel est trop trompeur, car laisse croire que l'on étudie la complexité d'un algorithme donnée (ce qui peut arriver), alors qu'il s'agit içi de la omplexité des problèmes. Le premier il y a le problème de confusion avec l'autre théorie que j'ai relevé tout à l'heure. Théorie de la complexité (informatique théorique) me parrait le plus acceptable. A voir ce qu'en dit TomT0m. --Pparent (d) 16 octobre 2012 à 00:05 (CEST)

Bon j'éffectue la scission, éventuellement le titre pourra être rechangé après, si nécessaire --Pparent (d) 16 octobre 2012 à 15:06 (CEST)

Théorie de la complexité (informatique théorique), Analyse de la complexité des algorithmes. Libre à vous d'améliorer ou de renommer. --Pparent (d) 16 octobre 2012 à 15:20 (CEST)

Désolé d'arriver après la bataille, mais je ne suis vraiment pas fan du nommage entre parenthèse. Il montre simplement qu'on ne sait pas comment nommer les choses de façon différentes (peut-être parce qu'elles sont fortement liées, et d'ailleurs généralement abordées dans un même cours par les enseignants). Je pense que le nom choisi "Théorie de la complexité (informatique théorique)" n'est pas très bon car les différents sujets que l'on veut séparer sont abordés en informatique théorique. --PierreSelim ^{[let discussion = fun _ ->]} 16 octobre 2012 à 15:26 (CEST)

Palette complexité

Bonjour, merci de donner votre avis sur Modèle:Palette Théorie de la complexité.

Cordialement, --Roll-Morton (d) 11 décembre 2012 à 12:20 (CET)

Restructuration de la partie "classes"

Bonjour,

je propose de revoir un peu la section qui énumère les classes : on pourrait peut-être faire quelque chose de plus général pour les classes indiquées (par exemple : "les classes sur machine déterministes en temps bornée sont définies par ... les grands exemples sont ...") et rajouter des choses notamment un mot sur les classes probabilistes (ZPP (complexité) etc. pour lesquelles j'ai commencé à faire des pages) et les classes "crypto" : PCP, IP, AM etc..

Qu'en pensez-vous ?

--Roll-Morton (d) 23 janvier 2013 à 17:50 (CET)

En fait, je ne vois pas bien ce que tu veux dire. Ce que je crois comprendre est que tu voudrais supprimer l'énumération des classes P, NP etc.. pour le remplacer par un paragraphe plus général qui décrit comment et sur quels critères sont définies les classes, et citer quelques grands exemples de classes, mais pas pas toutes. Le problème est qu'il n'y a pas (en général) d'article détaillé sur les classes, et que cet article est pour le moment le seul réceptacle d'informations précises et détaillées sur chaque classe. Mais je n'ai pas du comprendre ce que tu as voulu dire. L'idéal serait de dire : j'aimerais faire comme dans telle source par exemple. Cordialement --Jean-Christophe BENOIST (d) 23 janvier 2013 à 18:19 (CET)

C'est à peu près ça en fait ! Disons que je voulais rajouter des liens vers les articles ZPP (complexité) et compagnie, que j'essaye de créer ces temps-ci, mais en arrivant sur la page je me suis dit que rajouter des éléments à la liste allait rendre l'article encore plus difficile à digérer. Mais c'est vrai qu'il y a ici des infos sur les classes qu'il n'y a nulle part ailleurs et qu'il faut garder... Dans un premier temps je vais donc rajouter, et qui sait, peut-être y aura-t-il plus d'articles sur les classes un jour. --Roll-Morton (d) 23 janvier 2013 à 18:35 (CET)

Hum, maintenant il y a beaucoup d'articles sur les classes est-ce qu'on passe à l'autre modèle ? Idem est est-ce que l'on présente les classes de manière plus globale ?--Roll-Morton (discuter) 7 octobre 2013 à 17:49 (CEST)

Je le ferai dans un mois si il n'y a pas eu de réactions.--Roll-Morton (discuter) 27 janvier 2014 à 17:15 (CET)

Pas de problème pour moi. Tous mes encouragements ! Il faudrait tout de même conserver une énumération des classes, avec le lien interne, mais cela va de soi (?) Cordialement --Jean-Christophe BENOIST (discuter) 27 janvier 2014 à 17:58 (CET)

Oui bien sûr !--Roll-Morton (discuter) 27 janvier 2014 à 21:42 (CET)

Voilà c'est commencé. Il faudra sans doute adapter les parties précédentes (je ne les ai pas relues avant de réécrire la partie "classes", d'où des répétitions).--Roll-Morton (discuter) 8 mars 2014 à 13:56 (CET)

Modèle Complexity Zoo

Bonjour, un petit message pour signaler le modèle:Complexity Zoo qui permet mettre plus facilement des liens externes vers ... le Complexity Zoo. --Roll-Morton (d) 24 février 2013 à 10:32 (CET)

complexités : renvoi vers une autre discussion

Bonjour,

merci d'aller donner votre avis sur discussion portail : informatique théorique#complexités.

--Roll-Morton (discuter) 7 octobre 2013 à 17:46 (CEST)

Quantité de ressources

Les quantités de ressources sont déclinées en temps et espace. Quid de la quantité de ressources en énergie? Est-ce que cela ressortit aussi de la théorie de la complexité? --Pierre de Lyon (discuter) 8 mars 2014 à 17:15 (CET)

j’aurai tendance à dire que c'est fonction de la mémoire utilisée et du temps du calcul. Voire juste du nombre d'instructions si on considère que la lecture et l’écriture ont un coût et que le coût des lectures/écritures est borné par le nombre d'instructions pour exécuter l’algorithme. Donc la complexité en énergie (qui n'est pas définie pour une machine de Turing, donc ça n’a pas trop de sens) serait la même que la complexité en temps, asymptotiquement. Si on veut faire des vrais tests de coût énergétique après ça dépend de pas mal de facteurs de l’architecture et des algorithmes utilisés j’imagine ... — TomT0m ^[bla] 8 mars 2014 à 17:24 (CET)

Avec le calcul réversible (article anglais bien meilleurs, tiens, un article à améliorer), on peut atteindre - théoriquement - un coût en énergie nul. En revanche, je n'ai jamais rien vu concernant des classes de complexités énergétiques. --Jean-Christophe BENOIST (discuter) 8 mars 2014 à 17:58 (CET)

Ça ne me dit rien sur le plan théorique, par contre j'ai déjà vu des études expérimentales, notamment dans des contextes de calcul distribué.--Roll-Morton (discuter) 8 mars 2014 à 18:58 (CET)

Du côté théorique, il y a en:Landauer's principle. Zandr4^[Kupopo ?] 2 juillet 2014 à 09:48 (CEST)

Peut-on dire qu'il y a bien une notion de « ressource énergétique », mais qu'aucun résultat scientifique décisif n'a été obtenu? En conséquence on pourrait signaler ce type de ressource comme une piste potentielle de recherche. --Pierre de Lyon (discuter) 2 juillet 2014 à 10:05 (CEST)

J'ai plutôt l'impression qu'il y a un ensemble épars de résultats scientifiques, comme le principe de Landauer, mais qu'il reste à les organiser pour établir cette notion. Mais les bases semblent encore mouvantes, comme les débats sur le principe de Landauer, qui sont aussi lié aux débats (plus que centenaire) sur le démon de Maxwell, qui n'est pas encore clairement résolu. J'ai l'impression que si on se lance dans des recherches sur cette notion, on arrive très vite dans la thermodynamique, avec ses problèmes et paradoxes en cours, c'est très inter-disciplinaire. --Jean-Christophe BENOIST (discuter) 2 juillet 2014 à 10:19 (CEST)

Phrase incompréhensible

La phrase : « On qualifie de NP-difficile ou NP-complets (s'il appartient à NP) les problèmes décisionnels, c'est-à-dire ceux dont la réponse est de type binaire (oui/non, vrai/faux, 1/0, …). On qualifie parfois par convention de NP-difficiles les problèmes d'optimisation associés à un problème de décision NP-complets ou NP-difficile, c'est-à-dire que la réponse est de type numérique. » est du charabia pour moi. Je propose de la supprimer. --Pierre de Lyon (discuter) 1 juillet 2014 à 14:56 (CEST)

D'accord pour la suppression! --Pparent (discuter) 1 juillet 2014 à 15:16 (CEST)

D'accord aussi.--Roll-Morton (discuter) 1 juillet 2014 à 16:40 (CEST)

OK je supprime. --Pierre de Lyon (discuter) 2 juillet 2014 à 09:18 (CEST)

Rendre l'article plus pédagogique

Bonjour, j'ai rajouté l'exemple du voyageur de commerce. Dans l'ensemble, je trouve que l'article manque d'exemples. Aussi, je propose de ː

• de rajouter plus d'exemples
• de déplacer le gros des présentations des classes de complexité vers l'article "Classe de complexité"
• de fusionner la partie "introduction" et "problème algorithmique" (elles disent la même chose)
• Le texte est très indigeste des fois. Par exemple ː "Les problèmes C-difficiles sont les majorants de C et les problèmes C-complets sont les plus grands éléments de C.". Quel est l'intérêt de dire cela ? Puis plus loin "Quand on parle de problèmes P-complets ou P-difficiles on s'autorise uniquement des réductions dans LOGSPACE.". Alors que c'est dit nul part que les problèmes P-complets sont intuitivement les problèmes non parallélisables. Bref, des intuitions autour des définitions. Là, c'est un peu "brutal".

J'aimerai bien que l'on discute de tout cela. Qu'en pensez-vous ? --Fschwarzentruber (discuter) 31 mai 2016 à 23:52 (CEST)

En ce qui me concerne tu peux y aller, j'ai toujours reculé à reprendre cet article. --Roll-Morton (discuter) 1 juin 2016 à 08:54 (CEST)

Histoire de la Complexité

 Fschwarzentruber : a créé une section Histoire pour suggérer qu'une telle section devrait exister. A mon avis ça sera assez difficile à écrire, en la séparant de l'histoire de l'analyse d'algorithme. Donc il faudrait plutôt songer à écrire une article en soi-même qui s'intitulerait « Histoire de l'analyse d'algorithme et de leur complexité ». Ceci dit, je viens de jeter un coup d'oeil à la préface du livre « Selected Papers on Analysis of Algorithms » de Knuth où il explique comment le domaine de l'analyse d'algorithmes a eu du mal à émerger. Nous aurons donc du mal à en trouver les origines et cela risque d'être du travail inédit que nous devrions plutôt laisser aux historiens. En tout cas, je suis volontaire pour travailler sur ce projet d'Histoire de l'analyse d'algorithme et de leur complexité s'il voit le jour. A part les live de Knuth déjà cité, je ne connais pas d'autres références qui pourraient nous aider. Voir aussi à ce sujet la discussion sur la page d'Ada Lovelace à laquelle jai participé. --Pierre de Lyon (discuter) 3 octobre 2017 à 10:06 (CEST)

Bonjour Pierre, mon idée était d'avoir une section qui raconte dans les grandes avancées en théorie de la complexité. Qui a défini les premiers notions (NP-complétude, machines alternantes, etc.) et citer les grands théorèmes du domaine (Savitch, Toda, etc.) avec les années (avec les réf vers les papiers, voire en citant des textes qui racontent une histoire, on doit en trouver dans les bouquins de th. de la complexité, j'ai pas encore bien regardé). --Fschwarzentruber (discuter) 3 octobre 2017 à 11:10 (CEST)

Ça risque de ne pas être différent de la présentation des grands résultats. Du coup, je ne suis pas sûr que ça soit très intéressant et ça risque de n'être que des redites. --Pierre de Lyon (discuter) 3 octobre 2017 à 11:25 (CEST)

Je ne vois pas où les grands résultats sont présentés : théorème de Cook, de Savitch, de Toda, etc. Et tout ça, je pense que ça serait chouette de l'avoir raconté dans une section "Histoire". Non ? --Fschwarzentruber (discuter) 11 octobre 2017 à 19:15 (CEST)

Si on trouve une bonne source qui parle de l'histoire de la complexité, je pense que c'est une bonne idée, sinon ça risque d'être difficile, on a pas forcement le recul... --Roll-Morton (discuter) 11 octobre 2017 à 23:36 (CEST)

Je pense comme Roll-Morton que nous manquons de recul. Quand commence l'analyse d'algorithme et la complexité : avec Lamé, avec Gödel (et son intuition de problèmes NP-complets)? Il faudrait un ouvrage de référence qui à mon avis n'existe pas. --Pierre de Lyon (discuter) 12 octobre 2017 à 11:05 (CEST)

En cherchant un peu j'ai trouvé A Short History of Computational Complexity par Fortnow. Je n'ai pas encore vraiment regardé, je ne sais pas à quel point c'est utilisable, mais l'auteur est une référence. C'est souvent difficile d'expliquer le processus sans rentrer dans les détails (théorème de Toda, sans définir PP, #P, les oracles etc.), et j'ai peur que ce soit le cas dans ce texte. --Roll-Morton (discuter) 12 octobre 2017 à 14:09 (CEST)

Tout d'abord, merci pour cette référence. L'introduction doit être compréhensible de tous. Mais wikipedia est une encyclopédie : un article n'est pas un cours mais "doit" offrir un tour du sujet. Même si le lecteur non averti ne comprend pas tout, il a un aperçu global de l'histoire du domaine. --Fschwarzentruber (discuter) 12 octobre 2017 à 16:36 (CEST)

Oui oui, c'est sûr. Bon je pense que maintenant que l'on a une référence on peut faire quelque chose. Je dis juste qu'il ne faut pas que ça se transforme en une liste de pointeurs vers d'autres articles, et que c'est difficile.--Roll-Morton (discuter) 12 octobre 2017 à 17:10 (CEST)

Oui, l'avis de Pierre est intéressant aussi. L'aspect historique peut être dilué dans les autres sections aussi. Du coup, pas de nouvelle section mais juste une section sur les grands résultats en plus. Et pour le reste, on dilue. --Fschwarzentruber (discuter) 12 octobre 2017 à 18:27 (CEST)

Problèmes ouverts en complexité

Dans la liste des problèmes ouverts en complexité, il n'y a que des problèmes généraux, mais pas de problème particuliers et ça me gêne, Comme si la recherche en complexité n'était qu'affaire de grands problème type P=NP ! . J'entends par « particuliers » des problèmes comme la minimisation des fonctions convexes qui a été un grand problème ouvert de 47 à 79 ou le problème de l'isomorphisme de graphes. N'étant pas spécialiste de ces questions, je ne peux pas en être le rédacteur principal.--Pierre de Lyon (discuter) 12 octobre 2017 à 11:33 (CEST)

Pour l'isomorphisme de graphe je suis d'accord, mais pour le reste ça devient rapidement spécifique, et c'est difficile d'évaluer à quel point ce sont des problèmes remarquables qui méritent d'apparaître (on pourrait mettre des problème de bornes inf sur les circuits mais quels sont ceux qui sont emblématiques..?). Je pense qu'en générale une section «problème ouvert» n'est pas très encyclopédique, c'est plutôt du niveau recherche, mais dans notre cas il est impossible de ne pas parler de P=NP...--Roll-Morton (discuter) 12 octobre 2017 à 17:16 (CEST)

Je ne demande évidemment de ne pas parler des problèmes généraux (comme P=NP). je demande que l'on montre, par des exemples, que la théorie de la complexité s'intéresse aussi aux problèmes particuliers. Ceci dit, dire que le simplexe est spécifique c'est assez étonnant ! --Pierre de Lyon (discuter) 13 octobre 2017 à 10:26 (CEST)

Ah pardon, je n'avais pas compris ta remarque. Pour moi il y a quand même une distinction entre l'analyse d'algorithme qui s'intéresse à la complexité de problèmes spécifiques, et la théorie de la complexité qui est plus structurelle. Certes on s’intéresse parfois à des « problèmes clés » mais c'est surtout parce qu'ils ont une influence sur le tableau global. Enfin c'est mon point de vue. --Roll-Morton (discuter) 13 octobre 2017 à 14:10 (CEST)

Cette définition de théorie de la complexité est trop restrictive. On parle bien de la complexité de l'algorithme de tri et pas de son analyse. D'autre part, les liens sur la complexité d'algorithmes spécifiques, renvoient sur cet article, car c'est le seul qui parle de la complexité des algorithmes. Il y a donc quelque chose à faire. --Pierre de Lyon (discuter) 13 octobre 2017 à 15:03 (CEST)

La théorie de la complexité est généralement vue comme l'étude 1) la définition et l'étude de modèles de calcul 2) la classification des problèmes algorithmiques en fonction de leur complexité intrinsèque. (cf. Dexter C. Kozen, dans Theory of Computation, Lecture 1. p. 3). --Fschwarzentruber (discuter) 13 octobre 2017 à 15:22 (CEST)

Je veux bien, mais alors il faudra modifier les liens qui pointent vers cet article alors qu'ils devraient pointer vers un article analyse d'algorithme à créer. L'article Algorithmique ne remplit pas ce rôle. Pour ne donner qu'un exemple de mauvais lien, la section complexité algorithmique de l'article Algorithmique ne devrait pas dire que l'article développé est celui-ci, puisque comme vous venez de le dire, il ne traite pas d'analyse d'algorithmes spécifiques. --Pierre de Lyon (discuter) 13 octobre 2017 à 15:38 (CEST)

P. S. J'indique dans la discussion de l'article algorithmique ce qu'il faudrait mettre dans un article analyse d'algorithme. --Pierre de Lyon (discuter) 13 octobre 2017 à 15:44 (CEST)

Je vois. Juste deux remarques. 1) le domaine qui étude les algorithmes proprement dits (dont leurs complexités, etc.) s'appelle l'algorithmique. Y-a-t-il besoin d'un article sur la complexité des algos en particulier ? 2) Aussi, l'analyse d'un algo n'est pas déconnectée de la théorie de la complexité. L'analyse d'un algorithme donne une borne supérieure de complexité (par exemple, l'algo de tri fusion donne une borne supérieure en O(n log n) pour le problème du tri par comparaison). Du coup, ce n'est pas stupide de pointer ici aussi. --Fschwarzentruber (discuter) 13 octobre 2017 à 16:21 (CEST)

Pour ce qui est des liens, je fais souvent pointer vers complexité en temps qui me semble plus pertinent. Pour ce qui est de la position de la frontière, il est possible que je sois influencé par le vocabulaire anglo-saxon, qui n'est peut-être pas le même que le vocabulaire français. --Roll-Morton (discuter) 14 octobre 2017 à 15:08 (CEST)

Pour moi l'algorithmique est l'art d'écrire des algorithmes, pas l'art de les analyser en complexité. Regardez l'article algorithmique, il n'y a qu'une petite section sur la complexité. D'autre part, l'algorithmique et l'écriture des algorithmes ont existé bien avant qu'on les analyse en complexité (20 siècle entre l'algorithme d'Euclide et son analyse en complexité par Lamé). J"aurais envie de dire que vous avez un biais, probablement pour deux raisons: votre communauté scientifique est celle de la complexité abstraite, pas celle des livres de Knuth, ni celle de la sémantique et vous avez appris "en même temps" complexité et algorithmique. --Pierre de Lyon (discuter) 14 octobre 2017 à 15:42 (CEST)

Par défaut "complexité d'un problème=temps de calcul" ! … et ce n'est pas un point de vue mais le résumé des articles fr en de

« par défaut complexité d'un problème c'est temps de calcul ! … et ce n'est pas un point de vue mais le résumé des articles fr en de » est un argument d'autorité qui ne m'impressionne pas. Il faut donner une citation d'un auteur reconnu qui dit cela et pas seulement le mettre en commentaire d’une modification. Limiter la complexité à une complexité en temps est une attitude ringarde des années 1970. Aujourd'hui des travaux émergent pour considérer outre la complexité en espace, la complexité en énergie. En ces temps de COP26, pensons au gaspillage énergétique des algorithmes et des ordinateurs. Comme le fait remarquer Roll-Morton, il existe un article complexité en temps. Pierre de Lyon (discuter) 14 novembre 2021 à 16:45 (CET)

Les notations de Landau

Si on va sur l'article O, on est renvoyé à celui-ci, à propos des notations de Landau, or rien n'y est dit sur leur usage dans l'analyse de la complexité des algorithmes. Un vide à combler. Pierre de Lyon (discuter) 14 juin 2022 à 10:34 (CEST)