Théorie de la complexité...

[Nyothan]

Salut à tous,
J'aimerais lancer une discussion pour éclaircir la nature de la théorie de la complexité algorithmique;

Est-elle considérée comme une discipline mathématique à part entière ?
Est-ce autre chose que des maths ? de la la logique mathématique ?
Je n'arrive pas à vraiment à déterminer sa nature,
Il est vrai qu'on ne travaille pas dans le monde mathématique courant, mais il me semble tout de même que l'on étudie des "objets mathématisés", la conjecture P != NP fait tout de même partie des problème de l'institut clay....

:mur:

[SimonB]

Comme toutes les questions d'informatique théorique, le débat se pose. Je ne sais pas ce qu'est le "monde mathématique courant" ; mon cours de théorie des groupes et celui d'analyse complexe ne me semblent pas vivre a priori dans le même monde. Pourtant, je sais qu'à un certain moment (ou un certain niveau), un résultat de l'un va servir pour l'autre...
Pour la complexité, c'est pareil ! De plus en plus, dans un problème de maths, on a besoin d'une notion algorithmique. Typiquement, en arithmétique, qui se rapproche de plus en plus de la cryptographie...

[Nyothan]

Donc,selon toi, la théorie de la complexité serait une discipline mathématique à part entière ? Elle apparait souvent dans ce qu'on nomme "les mathématique discrètes", sous-entendu les maths de l'informatique.... qui également apparement définit de façon vague .....

La question est en fait de savoir ce que l'on entends par "mathématique"...
J'ai l'impression que la mathématique est la discipline qui à l'origine développe des outils (sous-entendu des théories ) pour étudier les structures telles que les entiers, les réels etc..... (et dans ce sens algèbre et analyse complexe, font partis du même monde ! )...

[ShakkaChan]

il arrive que la theorie de la complexité soit etudié dans les cour ou master de logique.
je pense c'est une theorie a l'intersection entre math et info comme celle du language de la decidabilité etc
les base ont etes posé par des logiciens avec des considerations mathematiques. doncje pense que oui c'est des math
quand a l'utilité la notion de complexité est tres utilisée en analyse numerique par exemple

[Stevh2o]

My 2cents :
L'informatique comme science dans son ensemble, et non pas technologie, fait partie des mathématiques au même titre que les probabilités par exemple.
Qq exemples :
1.Les bases de données relationnelles ( utilisées un peu partout qd même ! ) reposent sur l'algèbre relationnelle, qui s'appuie sur la théorie des ensembles : on touche qd même au fondation là.
2.Les langages et compilateurs doivent tout au travaux sur automates finis, langage formel, etc bref au travaux de Noam Chomsky (ok un linguiste, mais son travail est de nature mathématique) entre autres...

Pour la technologie, l'ordinateur n'est rien d'autre que la réunion de deux automates :
L'un mécanique ( la "pascaline", par ex) , l'autre logique (machine de Turing)
il me semble que même si la démarche n'est pas aussi rigoureuse d'une théorie mathématique, on n'est pas loin...

En ce qui concerne la question de la NP complétude, je la vois comme étant à la branche informatique ce que le Th de Fermat était à la théorie des nombres.
Au moins pour un point : je comprends le pb, mais je n'envisage même pas en rêve de comprendre un bout de tentative de démonstration ;)

S.