La théorie de la complexité computationnelle est un domaine des mathématiques et de l’informatique qui s’intéresse aux 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 leurs besoins en ressources. Les chercheurs classent les problèmes par difficulté et peuvent diviser les calculs en problèmes polynomiaux (P) et problèmes polynomiaux non terministes (NP).
La résolution d’un calcul nécessite des ressources telles que le temps, l’espace de stockage et le 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 devenir soluble avec l’aide de nouvelles technologies et de la recherche dans le domaine de la théorie de la complexité computationnelle. La ré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é computationnelle, un problème P est un problème qui peut être résolu en temps polynomial avec un algorithme simple. Cela 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 tant qu’un ordinateur dispose des ressources disponibles 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, comme des machines de Turing parallèles qui peuvent explorer plusieurs options. Le problème peut être résolu de cette façon, mais cela nécessitera 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 point de logique plutôt qu’une simple difficulté de calcul. Le problème du voyageur de commerce, dans lequel l’objectif est de trouver l’itinéraire le plus efficace entre un certain nombre de villes le long d’un itinéraire, est un exemple classique de problème NP en théorie de la complexité computationnelle.
La classification des problèmes P versus NP par le biais de la théorie de la complexité computationnelle peut être une tâche complexe, et les problèmes peuvent se déplacer d’un côté à l’autre de la division. Un petit ensemble de problèmes de calcul ne s’intègrent pas parfaitement dans l’une ou l’autre catégorie et sont parfois classés comme ni l’un ni l’autre afin de 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 qui ont une structure similaire. Dans d’autres, cependant, il peut s’agir d’un problème spécifique. Le processus d’exploration de tels programmes et de développement d’approches pour les résoudre est un domaine important des mathématiques et de l’informatique qui contribue au développement de systèmes informatiques avancés et puissants.