Calculabilité, complexités, classes de problèmes

Salut,

Je m'intéresse depuis assez récemment à l'une des théories qui constitue les fondements de l'informatique.

En particulier, tout ce qui concerne la calculabilité, le problème de l'arrêt (et sa preuve), le fonctionnement d'une machine de Turing, la définition des différentes classes de problème et la raison de ces choix, les preuves déjà établies d'inclusions de ces mêmes classes de problèmes, etc etc etc…

Cependant j'ai du mal à trouver des ressources sur le sujet et wikipédia ne me satisfait pas vraiment. Pourriez vous m'indiquer des lectures (papier ou en ligne) sur le sujet ?
Je cherche un document synthétique qui retrace tout les grands résultats (avec preuve si possible, si elle est à ma portée) de cette partie des mathématiques apparues très récemment (il y a 50-60 ans ?).

Je n'ai pas compris le choix de définition des classes de complexités (pourquoi celles-ci et pas d'autres ? Quelle en est la preuve ?), je n'ai toujours pas le moindre idée de ce que peut bien être une machine de Turing non déterministe, et j'aimerais comprendre la signification profonde de P=NP. La vulgarisation scientifique (et parfois philosophique) autour du sujet ne me satisfait plus et j'aimerais me frotter aux bases mathématiques concrètes de la question.

Si vous pouviez m'apporter des réponses j'en serais grandement ravi et je vous en remercie d'avance.

Salut, le Cormen possède une super explication sur le sujet qui n'utilise pas la notion de machine de Turing et qui est donc assez abordable dès qu'on a l'habitude de raisonner sur la complexité des algorithmiques.

La plupart des bouquins qui traitent le sujet, soit commencent par une introduction aux langages réguliers, hors contextes, à la complexité et enfin arrivent au sujet qui t'intéresse. Si ça ne te dérange pas de te familiariser avec ces concepts, tu peux te référer à ces notes de cours qui te donneront une bonne base mathématique. Si t'es courageux ou que tu veux en savoir plus, ce bouquin est très complet.

A un niveau plus philosophique, ce blog te donnera l'avis d'un chercheur et un tas d'articles sur des sujets relatifs à P=NP et à la théorie de la complexité en général.

Salut,

Peut-être que de véritables cours de licence te conviendraient ? Tu peux trouver les supports de mes cours de L3 ici :

• calculabilité
• complexité

(sur les pages des professeurs en question, tu peux trouver d’autre supports agencés différement suite à des réorganisations du cours « calculabilité – complexité » selon les années). Ce sont des supports de cours, donc plutôt formels, mais ils se suffisent à eux-mêmes bien que ça ne vaille évidemment pas un cours avec le prof en chair et en os. Et puis comme c’est un cours d’un semestre, c’est long. En tout cas, tu y trouveras tout ce dont tu parles (entre autres !), et la plupart des résultats sont accompagnés de preuves.

Édit : Bon, je n’avais pas vu que tu demandais un truc « synthétique », du coup ça correspond pas du tout… Je laisse quand même au cas où.

Au contraire, c'est tout à fait ce que je cherche !

Merci à toi Maëlan !

Merci également à toi cyru, je suis en train de lire ton premier document, et il correspond aussi à mes attentes.

@Algue-Rythme, tu as ce cough magnifique article sur des erreurs classiques sur la classe de complexite et donc, avec la definition formelle pour comprendre deux erreurs typiques lies a une definition non formelle de la complexite.

Ceci dit, la raison historique de la classe P et NP par rapport a la relation de reduction polynomiale provient du fait que l'on pensait que les problemes dont un algorithme avait un temps d'execution borne par un polynome etaient facile a resoudre (ce qui est vrai jusqu'a une certaine limite) et les autres difficiles (ce qui est faux, jusqu'a une certaine limite). On sait aujourd'hui que ce n'est pas cette notion qui est importante. La notion importante pour determiner si un probleme est dur ou non c'est la notion de convexite.

J'ecrirais peut etre un truc a ce sujet rapidemment mais typiquement, tu peux avoir un exemple d'un meme probleme qui passe de facile a dur en changeant les contraintes de convexe a concave (le cas limite etant lineaire) ici, dans l'introduction. Au passage, cet exercice propose est un probleme PSPACE-complet, ou PSPACE est une classe encore plus vaste que NP.

Les cours de http://wandida.com/fr/Topic/machine-de-turing (et autre en naviguant sur le site) font une très bonne intro au sujet aussi !

Si tu écris quelque chose là-dessus, je suis preneur !