human
Veuillez expliquer ce qu'est "intraitabilité (complexité)"
gpt
En informatique théorique et en mathématiques, la théorie de la complexité computationnelle se concentre sur la classification des problèmes de calcul en fonction de leur utilisation des ressources et sur la relation entre ces classes. Un problème de calcul est une tâche résolue par un ordinateur. Un problème de calcul peut être résolu par l'application mécanique d'étapes mathématiques, comme 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 en quantifiant leur complexité de calcul, 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é dans le calcul parallèle). L'un des rôles de la théorie de la complexité computationnelle est de 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é computationnelle.
Les domaines étroitement liés de l'informatique théorique sont l'analyse des algorithmes et la théorie de la calculabilité. Une distinction clé entre l'analyse des algorithmes et la théorie de la complexité computationnelle est 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 seconde pose une question plus générale sur tous les algorithmes possibles qui pourraient être utilisés pour résoudre le même problème. Plus précisément, la théorie de la complexité computationnelle tente de classer les problèmes qui peuvent ou ne peuvent pas être résolus avec des ressources restreintes de manière appropriée. À son tour, imposer des restrictions sur les ressources disponibles est ce qui distingue la complexité computationnelle de la théorie de la calculabilité : cette dernière théorie demande quels types de problèmes peuvent, en principe, être résolus de manière algorithmique.