Discuter:Théorie de la complexité

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Théorie de la complexité fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet.
WikiProjet Informatique
 Théorie de la complexité fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Bon début Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Maximum Cet article a été classé comme d'Importance maximum selon le Tableau d'évaluation du projet. (Contester?)

Sommaire

[modifier] Erreur

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 (d · c), 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)

[modifier] 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)

[modifier] 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.

[modifier] 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)

[modifier] 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(nc) 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.

[modifier] 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)

[modifier] 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)

[modifier] 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)

[modifier] 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)

[modifier] 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)