Quelle est la théorie de la complexité informatique?

La théorie de la complexité informatique est un domaine de mathématiques et d'informatique qui concerne les ressources nécessaires pour résoudre les problèmes d'un système informatique.Un certain nombre de techniques sont disponibles pour déterminer les exigences des ressources d'un problème.Certains problèmes pourraient ne pas être réalisables sur les systèmes informatiques existants en raison de leurs demandes de ressources.Les chercheurs classent les problèmes par difficulté et peuvent diviser les calculs en problèmes polynomiaux polynomiaux par rapport aux problèmes polynomiaux (NP) non terministes.

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 n'a pas les ressources disponibles.À mesure que la technologie informatique s'améliore, un problème auparavant insoluble pourrait devenir résoluble à l'aide de nouvelles technologies et de recherches 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 sur les algorithmes utilisés pour le résoudre.

Dans la théorie de la complexité de calcul, 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 elle est à la fois résoluble et vérifiable par ordinateur.De tels problèmes pourraient être considérés comme rapidement résolubles tant qu'un ordinateur a les ressources disponibles pour gérer les calculs nécessaires.

Les problèmes 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 des machines de Turing parallèles qui peuvent explorer plusieurs options.Le problème peut être résoluble de cette façon, mais il nécessitera beaucoup plus de ressources.De tels problèmes peuvent être plus faciles pour les opérateurs humains capables de penser logique avancée, car le point de basculement est souvent celui de la logique plutôt que de la difficulté de calcul.Le problème des vendeurs itinérants, 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 d'un problème de NP dans la théorie de la complexité de calcul.

Classification des problèmes P contre NP par la théorie de la complexité informatiquePeut être une tâche complexe et les problèmes peuvent se déplacer dans les deux sens à travers le fossé.Un petit ensemble de problèmes de calcul ne correspond pas bien à l'une ou l'autre catégorie et ne sont parfois classés comme ni 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 qui ont une structure similaire.Dans d'autres, cependant, cela pourrait être spécifique au problème.Le processus d'exploration de ces 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 de haute puissance.