Complexité
L'étude de la complexité a pour but de quantifier la mesure d'une solution à un problème donné. En général, cette quantification se fait par les paramètres temps et espace.
Sachez qu'il y a des problèmes pour lesquels on connait des réponses et d'autres pour lesquels on ne connait pas de réponses.
La complexité a été étudié à travers un modèle de calcul. Bien qu'il en existe plusieurs, le plus utilisé est sans doute la machine de Turing.
Cette dernière permet d’étudier la décidabilité des programmes : ce qui peut être fait par un ordinateur et ce qui ne peut l’être.
Elle permet aussi de distinguer les problèmes possibles ( polynomiales) et non possibles (exponentielles)
La complexité consiste essentiellement à étudier les problèmes de décision. Ces derniers reviennent le plus souvent à tester l'appartenance d'un élément à un langage dans son sens mathématique.
D'une manière générale, on définit TIME(t(n)) comme étant la classe de complexité relative à l'ensemble des langages L tels que L peut être décidé en temps t(n) par une machine de Turing déterministe.
NTIME(t(n)) est celle relative à l'ensemble des langages L tels que L peut être décidé en temps t(n) par une machine de Turing non déterministe.
Les classes importantes sont celles des problèmes qui peuvent être résolus en temps polynomial par une machine de Turing déterministe (Classe P) et non déterministe (Classe NP).
Jusqu' à preuve du contraire P ÍNP. En effet, la question P=NP ? reste encore ouverte après plus de 40 ans d’effort.
Un problème NP-complet est un problème parmi les plus difficiles de la classe NP. Il est tel que tout autre problème de la classe NP peut se réduire à lui.
Une réduction permet de ramener la décidabilité d'un problème à celle d'un autre. Elle fait correspondre à une instance du problème A une instance du problème B avec même réponse et calculable en temps polynomial.
Un des plus importants résultats en théorie de la complexité est celui de Stephen Cook (1971) qui montre le premier problème NP-complet ( SAT ) et dont la démonstration est basée sur la machine de Turing.