Théorie de la complexité
La théorie de la complexité numérique s'attache à classer les problèmes informatiques en fonction de leur difficulté inhérente et à les relier les uns aux autres. Un problème informatique est une tâche résolue par un ordinateur. Un problème de calcul peut être résolu par application mécanique d'étapes mathématiques, telles qu'un algorithme.
Un problème est considéré comme intrinsèquement difficile si sa solution nécessite des ressources importantes, quel que soit l'algorithme utilisé. La théorie formalise cette intuition en introduisant des modèles mathématiques de calcul pour étudier ces problèmes et quantifier leur complexité, c'est-à-dire la quantité de ressources nécessaires pour les résoudre, telles que le temps et le stockage. D'autres mesures de complexité sont également utilisées, telles que la quantité de communication (utilisée dans la complexité de la communication), le nombre de portes dans un circuit (utilisé dans la complexité du circuit) et le nombre de processeurs (utilisés dans le calcul parallèle). L'un des rôles de la théorie de la complexité informatique consiste à déterminer les limites pratiques de ce que les ordinateurs peuvent et ne peuvent pas faire. Le problème P versus NP, l'un des sept problèmes du Prix du Millénaire, est dédié au domaine de la complexité informatique.
L’analyse des algorithmes et la théorie de la calculabilité sont des domaines étroitement liés en informatique théorique . Une distinction essentielle entre l'analyse des algorithmes et la théorie de la complexité de calcul réside dans le fait que la première est consacrée à l'analyse de la quantité de ressources nécessaires à un algorithme particulier pour résoudre un problème, tandis que la dernière pose une question plus générale sur tous les algorithmes possibles. utilisé pour résoudre le même problème. Plus précisément, la théorie de la complexité informatique tente de classer les problèmes qui peuvent ou ne peuvent pas être résolus avec des ressources limitées en conséquence. Ce qui différencie à son tour la complexité informatique de la théorie de la calculabilité, c'est l'imposition de restrictions sur les ressources disponibles : cette dernière théorie demande quel type de problèmes peuvent, par exemple, être résolus par un algorithme.
