Qu'est-ce que la théorie de la complexité informatique?
La théorie de la complexité informatique est un domaine des mathématiques et de l'informatique qui se préoccupe des ressources nécessaires pour résoudre des problèmes sur un système informatique. Un certain nombre de techniques sont disponibles pour déterminer les besoins en ressources d'un problème. Certains problèmes peuvent ne pas être réalisables sur les systèmes informatiques existants en raison de la demande en ressources. Les chercheurs classent les problèmes par difficulté et peuvent diviser les calculs en problèmes polynomiaux (P) et polynomiaux non finaliseurs (NP).
La résolution d'un calcul nécessite des ressources telles que du temps, de l'espace de stockage et du matériel. Un système informatique peut avoir des limitations qui rendent un problème fonctionnellement impossible à résoudre car il ne dispose pas des ressources disponibles. À mesure que la technologie informatique s'améliore, un problème auparavant insoluble pourrait le devenir grâce aux nouvelles technologies et à la recherche dans le domaine de la théorie de la complexité informatique. La solvabilité d'un problème n'est pas nécessairement déterminée par sa complexité, mais par les algorithmes utilisés pour le résoudre.
Dans la théorie de la complexité informatique, un problème P est un problème qui peut être résolu en temps polynomial avec un algorithme simple. Il peut encore nécessiter des ressources substantielles, mais il est à la fois résoluble et vérifiable par ordinateur. De tels problèmes pourraient être considérés comme pouvant être résolus rapidement, à condition qu'un ordinateur dispose des ressources nécessaires pour gérer les calculs nécessaires.
Les problèmes de NP sont plus complexes. Il n'est pas possible d'appliquer un seul algorithme et il peut être nécessaire d'utiliser des options plus avancées, telles que les machines de Turing en parallèle, pouvant explorer plusieurs options. Le problème pourrait être résolu de cette façon, mais il faudra beaucoup plus de ressources. De tels problèmes pourraient être plus faciles pour les opérateurs humains qui sont capables d'une pensée logique avancée, car le point de basculement est souvent un problème de logique plutôt qu'une simple difficulté de calcul. Le problème du voyageur de commerce, dont l'objectif est de trouver l'itinéraire le plus efficace entre plusieurs villes le long d'un itinéraire, est un exemple classique d'un problème de NP dans la théorie de la complexité de calcul.
La classification des problèmes de P par rapport à NP par le biais de la théorie de la complexité informatique peut être une tâche complexe et les problèmes peuvent évoluer de part et d'autre de la fracture. Une petite série de problèmes de calcul ne rentrent parfaitement dans aucune des deux catégories et sont parfois classés comme tels pour refléter cela. Il pourrait éventuellement être possible de développer un algorithme pour résoudre un problème NP, et dans certains cas, il pourrait s’appliquer à d’autres problèmes ayant une structure similaire. Dans d'autres, cependant, cela peut être spécifique à un problème. L’exploration de tels programmes et la mise au point d’approches pour les résoudre constituent un domaine important des mathématiques et de l’informatique qui contribuent au développement de systèmes informatiques avancés de haute puissance.