Classes de complexité temporelle et spatiale

Les classes de complexité regroupent les problèmes de décision en fonction du temps ou de la mémoire nécessaires à une machine pour les résoudre, organisant ainsi le calcul dans un paysage structuré allant de l'espace logarithmique au temps exponentiel.

Definition

Une classe de complexité est l'ensemble des problèmes résolubles dans une limite spécifiée pour une ressource, généralement le temps ou la mémoire de travail utilisée par une machine de Turing en fonction de la longueur de l'entrée, avec des variantes déterministes et non déterministes pour chaque ressource.

Scope

Ce sujet couvre la définition des classes de complexité temporelle et spatiale déterministes et non déterministes telles que P, NP, L, NL, PSPACE et EXPTIME, les théorèmes de hiérarchie qui les séparent, les inclusions et les relations connues entre elles, le théorème de Savitch reliant l'espace non déterministe et déterministe, ainsi que les problèmes complets qui caractérisent chaque classe.

Core questions

• Comment les problèmes sont-ils regroupés en fonction du temps et de la mémoire nécessaires à leur résolution ?
• Quelles inclusions parmi les classes de complexité standard sont connues pour être strictes ?
• Comment l'espace non déterministe se rapporte-t-il à l'espace déterministe ?
• Quel rôle les problèmes complets jouent-ils dans la caractérisation d'une classe ?

Key theories

Théorèmes de hiérarchie

Avec asymptotiquement plus de temps ou d'espace, une machine peut décider strictement plus de langages ; ainsi, les classes de temps et d'espace forment des hiérarchies propres, et les ressources ne peuvent être gaspillées sans perdre de problèmes.

Théorème de Savitch

Tout problème résoluble en espace non déterministe peut être résolu de manière déterministe en utilisant seulement le carré de cet espace ; ainsi, pour la mémoire, contrairement à ce qui semble être le cas pour le temps, le non-déterminisme n'offre qu'un avantage modeste au maximum.

Clinical relevance

Placer un problème dans une classe de complexité indique aux praticiens à quoi s'attendre : les problèmes de la classe P s'adaptent aux grandes entrées, les problèmes PSPACE-complets, tels que de nombreux jeux et tâches de planification, résistent à une solution efficace, et la structure de la classe guide la recherche d'algorithmes exacts, d'approximations, ou la refonte du problème.

History

Hartmanis et Stearns ont défini les classes bornées en temps et prouvé le théorème de hiérarchie temporelle en 1965, fondant ainsi le domaine. La complexité spatiale a été développée en parallèle, avec le théorème de Savitch en 1970 et des résultats ultérieurs tels que la fermeture de l'espace non déterministe sous le complément par Immerman et Szelepcsényi, affinant ainsi la compréhension.

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

Quelle est la différence entre la complexité temporelle et spatiale ?

La complexité temporelle compte le nombre d'étapes qu'un algorithme effectue, tandis que la complexité spatiale mesure la mémoire de travail qu'il utilise. Elles se comportent différemment : l'espace peut être réutilisé au fur et à mesure qu'un calcul progresse, c'est pourquoi l'espace non déterministe est beaucoup moins puissant par rapport à l'espace déterministe que ce que la comparaison analogue pour le temps semble indiquer.

Pourquoi les théorèmes de hiérarchie sont-ils importants ?

Ils prouvent que davantage de ressources permettent véritablement de résoudre plus de problèmes, excluant la possibilité que toutes les classes se confondent en une seule. Cela garantit, par exemple, qu'il existe des problèmes résolubles en temps exponentiel mais pas en temps polynomial, ancrant ainsi tout l'édifice des classes de complexité.