Worldlex Wiki 
En théorie de la complexité computationnelle , une classe de complexité est un ensemble de problèmes de calcul « de complexité liée aux ressources ». Les deux ressources les plus couramment analysées sont le temps et la mémoire .
En général, une classe de complexité est définie en fonction d'un type de problème de calcul, d'un modèle de calcul et d'une ressource limitée, comme le temps ou la mémoire . Plus précisément, la plupart des classes de complexité regroupent les problèmes de décision résolubles par une machine de Turing et se distinguent par leurs exigences en temps ou en espace (mémoire). Par exemple, la classe P est l'ensemble des problèmes de décision résolubles par une machine de Turing déterministe en temps polynomial . Il existe cependant de nombreuses classes de complexité définies en fonction d'autres types de problèmes (par exemple, les problèmes de dénombrement et les problèmes de fonctions ) et utilisant d'autres modèles de calcul (par exemple, les machines de Turing probabilistes , les systèmes de preuve interactifs , les circuits booléens et les ordinateurs quantiques ).
L'étude des relations entre les classes de complexité est un domaine de recherche majeur en informatique théorique . Il existe souvent des hiérarchies générales de classes de complexité ; par exemple, on sait que plusieurs classes fondamentales de complexité temporelle et spatiale sont liées entre elles de la manière suivante :
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE
Où ⊆ désigne la relation d'inclusion . Cependant, de nombreuses relations restent encore inconnues ; par exemple, l'un des problèmes ouverts les plus célèbres en informatique porte sur la question de savoir si P est égal à NP . Les relations entre les classes permettent souvent de répondre à des questions sur la nature fondamentale du calcul. Le problème P versus NP , par exemple, est directement lié à la question de savoir si le non-déterminisme accroît la puissance de calcul des ordinateurs et si les problèmes dont les solutions peuvent être rapidement vérifiées peuvent également être résolus rapidement.
des ensembles de problèmes de calcul apparentés . Elles sont définies en fonction de la difficulté de calcul des problèmes qu'elles contiennent, relativement à des ressources de calcul particulières.Par exemple, le temps ou la mémoire. Plus formellement, la définition d'une classe de complexité repose sur trois éléments : un type de problème de calcul, un modèle de calcul et une ressource de calcul bornée. En particulier, la plupart des classes de complexité regroupent les problèmes de décision résolubles par une machine de Turing disposant de ressources temporelles ou spatiales bornées . Par exemple, la classe de complexité P est définie comme l'ensemble des problèmes de décision résolubles par une machine de Turing déterministe en temps polynomial .Problèmes de calcul
Intuitivement, un problème de calcul est simplement une question qui peut être résolue par un algorithme . Par exemple, « le nombre naturel λ est -il premier ? » est un problème de calcul. Mathématiquement, un problème de calcul est représenté par l' ensemble des solutions à ce problème. Dans l'exemple de la primalité, le problème (appelons-le λ ) est représenté par l'ensemble de tous les nombres naturels premiers : λ ∈ ℝ . En théorie du calcul, ces solutions sont représentées par des chaînes de caractères ; par exemple, dans le cas de la primalité, les nombres naturels pourraient être représentés par des chaînes de bits représentant des nombres binaires . C'est pourquoi les problèmes de calcul sont souvent appelés, de manière synonyme, des langages, puisque les chaînes de bits représentent des langages formels (un concept emprunté à la linguistique ) ; par exemple, dire que le problème est de classe de complexité P est équivalent à dire que le langage est de classe P.
Problèmes de décision
Les problèmes les plus fréquemment analysés en informatique théorique sont les problèmes de décision , c'est-à-dire les problèmes qui peuvent être formulés comme des questions fermées (oui/non ). L'exemple de primalité mentionné plus haut illustre un problème de décision, car il peut être représenté par la question fermée : « Le nombre naturel est- il premier ? ». En termes de théorie du calcul, un problème de décision est représenté par l'ensemble des chaînes de caractères auxquelles un ordinateur exécutant un algorithme correct répondrait « oui ». Dans l'exemple de primalité, il s'agit de l'ensemble des chaînes de caractères représentant des nombres naturels qui, lorsqu'elles sont entrées dans un ordinateur exécutant un algorithme testant correctement la primalité , obtiennent la réponse « oui, ce nombre est premier ». Ce format « oui/non » est souvent exprimé de manière équivalente par le terme « acceptation/rejet » : un algorithme « accepte » une chaîne de caractères si la réponse au problème de décision est « oui » et la « rejette » si la réponse est « non ».
Bien que certains problèmes ne puissent être facilement formulés comme des problèmes de décision, ils englobent néanmoins un large éventail de problèmes de calcul. Parmi les autres types de problèmes à partir desquels certaines classes de complexité sont définies, on peut citer :
- Problèmes de fonctionnement (par exemple, FP )
- Problèmes de dénombrement (ex. #P )
- Problèmes d'optimisation
- Problèmes liés aux promesses (voir la section « Autres types de problèmes »)
Modèles informatiques
Pour concrétiser la notion d’« ordinateur », les problèmes d’informatique théorique sont analysés dans le cadre d’un modèle computationnel . Ces modèles formalisent les notions de ressources de calcul telles que le « temps » et la « mémoire ». En théorie de la complexité algorithmique , les classes de complexité traitent des besoins en ressources inhérents aux problèmes, et non de ceux qui dépendent de la construction physique de l’ordinateur. Par exemple, dans la réalité, différents ordinateurs peuvent nécessiter des quantités différentes de temps et de mémoire pour résoudre un même problème, en raison de leur conception. En fournissant des représentations mathématiques abstraites des ordinateurs, les modèles computationnels s’affranchissent des complexités superflues du monde réel (comme les différences de vitesse des processeurs ) qui entravent la compréhension des principes fondamentaux.
Le modèle de calcul le plus couramment utilisé est la machine de Turing . Bien que d'autres modèles existent et que de nombreuses classes de complexité soient définies à partir de ceux-ci (voir la section « Autres modèles de calcul » ), la machine de Turing sert à définir la plupart des classes de complexité fondamentales. Avec la machine de Turing, au lieu d'utiliser des unités de temps standard comme la seconde (qui rendent impossible la distinction entre le temps d'exécution et la vitesse du matériel) et des unités de mémoire standard comme l'octet , la notion de temps est abstraite comme le nombre d'étapes élémentaires effectuées par la machine de Turing pour résoudre un problème, et la notion de mémoire est abstraite comme le nombre de cellules utilisées sur le ruban de la machine. Ces notions sont expliquées plus en détail ci-dessous.
Il est également possible d'utiliser les axiomes de Blum pour définir des classes de complexité sans faire référence à un modèle de calcul concret , mais cette approche est moins fréquemment utilisée en théorie de la complexité.
Machines de Turing déterministes
Une machine de Turing est un modèle mathématique d'un ordinateur général. C'est le modèle le plus couramment utilisé en théorie de la complexité, notamment parce qu'il est considéré comme aussi puissant que n'importe quel autre modèle de calcul et qu'il est facile à analyser mathématiquement. Surtout, on pense que s'il existe un algorithme qui résout un problème particulier, alors il existe également une machine de Turing qui résout ce même problème (c'est ce qu'on appelle la thèse de Church-Turing ) ; cela signifie que l'on pense que tout algorithme peut être représenté par une machine de Turing.
Mécaniquement, une machine de Turing (MT) manipule des symboles (généralement limités aux bits 0 et 1 pour une meilleure compréhension des ordinateurs) stockés sur une bande magnétique de longueur infinie. La MT peut lire et écrire, un symbole à la fois, grâce à une tête de lecture/écriture. Son fonctionnement est entièrement déterminé par un ensemble fini d'instructions élémentaires, telles que : « dans l'état 42, si le symbole rencontré est 0, écrire 1 ; si le symbole rencontré est 1, passer à l'état 17 ; dans l'état 17, si le symbole rencontré est 0, écrire 1 et passer à l'état 6 ». La machine de Turing démarre avec uniquement la chaîne d'entrée sur sa bande, le reste étant vierge. Elle accepte l'entrée si elle atteint un état d'acceptation désigné et la rejette dans le cas contraire. La machine de Turing déterministe (MTD) est le type le plus simple. Elle utilise un ensemble fixe de règles pour déterminer ses actions futures (d'où son appellation de « déterministe »).
Un problème de calcul peut être défini, en termes de machine de Turing, comme l'ensemble des chaînes de caractères d'entrée qu'une machine de Turing particulière accepte. Par exemple, le problème de primalité mentionné précédemment correspond à l'ensemble des chaînes (représentant les nombres naturels) acceptées par une machine de Turing exécutant un algorithme qui teste correctement la primalité . On dit qu'une machine de Turing reconnaît un langage (rappelons que « problème » et « langage » sont largement synonymes en calculabilité et en théorie de la complexité) si elle accepte toutes les entrées appartenant à ce langage, et qu'elle décide du langage si, de plus, elle rejette toutes les entrées n'appartenant pas à ce langage (certaines entrées peuvent entraîner un exécution infinie de la machine de Turing ; la décidabilité impose donc la contrainte supplémentaire, par rapport à la reconnaissance , que la machine de Turing doit s'arrêter pour toutes les entrées). Une machine de Turing qui « résout » un problème est généralement une machine qui décide du langage.
Les machines de Turing permettent de se familiariser intuitivement avec les notions de « temps » et d'« espace ». La complexité temporelle d'une machine de Turing pour une entrée donnée correspond au nombre d'étapes élémentaires nécessaires pour atteindre un état d'acceptation ou de rejet. Sa complexité spatiale correspond au nombre de cellules de son ruban utilisées pour atteindre un état d'acceptation ou de rejet.
Machines de Turing non déterministes
La machine de Turing déterministe (MTD) est une variante de la machine de Turing non déterministe (MNT). Intuitivement, une MNT est une machine de Turing classique dotée de la capacité supplémentaire d'explorer plusieurs actions futures possibles à partir d'un état donné et de « choisir » une branche qui accepte l'entrée (le cas échéant). Ainsi, alors qu'une MTD ne peut suivre qu'une seule branche de calcul, une MNT peut être imaginée comme un arbre de calcul, se ramifiant à chaque étape en de nombreux chemins de calcul possibles (voir image). Si au moins une branche de l'arbre s'arrête avec une condition d'« acceptation », alors la MNT accepte l'entrée. De cette manière, une MNT peut être vue comme explorant simultanément toutes les possibilités de calcul en parallèle et sélectionnant une branche acceptante. Les MNT ne sont pas conçues pour être des modèles physiquement réalisables ; ce sont simplement des machines abstraites théoriquement intéressantes qui donnent lieu à un certain nombre de classes de complexité intéressantes (qui ont souvent des définitions équivalentes physiquement réalisables).
La complexité temporelle d'une machine de Turing non linéaire (MTN) correspond au nombre maximal d'étapes nécessaires à l'exécution de chaque branche de son calcul. De même, sa complexité spatiale correspond au nombre maximal de cellules nécessaires à l'exécution de chaque branche de son calcul.
Les DTM peuvent être considérés comme un cas particulier de NTM qui n'exploitent pas le non-déterminisme. Par conséquent, tout calcul réalisable par un DTM peut également l'être par un NTM équivalent. Il est également possible de simuler n'importe quel NTM à l'aide d'un DTM (ce dernier calculant simplement chaque branche de calcul possible, une à une). Ainsi, les deux sont équivalents en termes de calculabilité. Cependant, la simulation d'un NTM avec un DTM requiert souvent davantage de temps et/ou de ressources mémoire ; comme nous le verrons, l'importance de ce ralentissement pour certaines classes de problèmes de calcul est une question fondamentale en théorie de la complexité algorithmique.
limites des ressources
Les classes de complexité regroupent les problèmes de calcul selon leurs besoins en ressources. Pour ce faire, on différencie les problèmes par des bornes supérieures sur la quantité maximale de ressources nécessaires à la résolution par l'algorithme le plus efficace. Plus précisément, les classes de complexité s'intéressent au taux de croissance des ressources requises pour résoudre un problème donné lorsque la taille des données d'entrée augmente. Par exemple, le temps de résolution des problèmes de la classe P croît polynomialement avec la taille des données d'entrée, ce qui est relativement faible comparé aux problèmes de la classe exponentielle EXPTIME (ou plus précisément, aux problèmes de EXPTIME qui ne font pas partie de P ) .
Il convient de noter que l'étude des classes de complexité vise principalement à comprendre la complexité intrinsèque nécessaire à la résolution des problèmes de calcul. Les théoriciens de la complexité s'intéressent donc généralement à déterminer la classe de complexité minimale à laquelle appartient un problème et, par conséquent, à identifier la classe à laquelle appartient un problème de calcul grâce à l'algorithme le plus efficace . Il peut exister, par exemple, un algorithme qui résout un problème particulier en temps exponentiel, mais si l'algorithme le plus efficace pour résoudre ce problème s'exécute en temps polynomial, alors la complexité temporelle intrinsèque de ce problème est mieux décrite comme polynomiale.
limites temporelles
limites spatiales
classes de complexité de base
- La classe de complexité temporelle est l'ensemble de tous les problèmes qui sont résolus par une machine de Turing déterministe en temps.
- La classe de complexité temporelle est l'ensemble de tous les problèmes qui sont résolus par une machine de Turing non déterministe en temps.
- La classe de complexité spatiale est l'ensemble de tous les problèmes qui sont résolus par une machine de Turing déterministe spatiale.
- La classe de complexité spatiale est l'ensemble de tous les problèmes qui sont résolus par une machine de Turing spatiale non déterministe.
classes de complexité temporelle
On dit souvent que P est la classe des problèmes qui peuvent être résolus « rapidement » ou « efficacement » par un ordinateur déterministe, car la complexité temporelle de la résolution d'un problème dans P augmente relativement lentement avec la taille de l'entrée.
Une caractéristique importante de la classe NP est qu'elle peut être définie de manière équivalente comme la classe des problèmes dont les solutions sont vérifiables par une machine de Turing déterministe en temps polynomial. Autrement dit, un langage appartient à NP s'il existe une machine de Turing déterministe en temps polynomial, appelée vérificateur, qui prend en entrée une chaîne de caractères et une chaîne de certificat de taille polynomiale , et qui accepte si la chaîne appartient au langage et la rejette dans le cas contraire. Intuitivement, le certificat sert de preuve que l'entrée appartient au langage. Formellement :
- NP est la classe des langages pour lesquels il existe une machine de Turing déterministe en temps polynomial et un polynôme tel que pour tout , appartient à si et seulement s'il existe un tel que accepte.
Cette équivalence entre la définition non déterministe et la définition par vérificateur met en lumière un lien fondamental entre non-déterminisme et vérifiabilité des solutions. De plus, elle fournit une méthode utile pour prouver qu'un langage appartient à NPP versus NP . On sait que (intuitivement, les machines de Turing déterministes ne sont qu'une sous-classe des machines de Turing non déterministes qui n'exploitent pas leur non-déterminisme ; ou, selon la définition du vérificateur, P est la classe des problèmes dont les vérificateurs en temps polynomial n'ont besoin que de recevoir la chaîne vide comme certificat), on ignore si NP est strictement supérieur à P. Si P = NP , alors le non-déterminisme n'apporte aucun gain de puissance de calcul par rapport au déterminisme quant à la capacité à trouver rapidement une solution à un problème ; autrement dit, explorer toutes les branches de calcul possibles n'offre au plus qu'un gain de vitesse polynomial par rapport à l'exploration d'une seule branche. De plus, il s'ensuit que s'il existe une preuve pour une instance de problème et que cette preuve peut être rapidement vérifiée (c'est-à-dire si le problème appartient à NP ), alors il existe également un algorithme capable de construire rapidement cette preuve (c'est-à-dire si le problème appartient à P ). Cependant, la grande majorité des informaticiens pensent que non , et la plupart des schémas cryptographiques utilisés aujourd'hui reposent sur l'hypothèse que non .
EXPTIME et NEXPTIME
classes de complexité spatiale
PSPACE et NPSPACE
Bien que l'on ignore si P = NP , le théorème de Savitch a démontré que PSPACE = NPSPACE . On sait également que PSPACE = NPSPACE , ce qui découle intuitivement du fait que, l'écriture dans une cellule du ruban d'une machine de Turing prenant une unité de temps, une machine de Turing fonctionnant en temps polynomial ne peut écrire que dans un nombre polynomial de cellules. On suppose que P est strictement inférieur à PSPACE , mais cela n'a pas été prouvé.
EXPSPACE et NEXPSPACE
Le théorème de Savitch a démontré que EXPSPACE = NEXPSPACE . Cette classe est extrêmement large : elle est connue pour être un sur-ensemble strict de PSPACE , NP et P , et on pense qu'elle est un sur-ensemble strict de EXPTIME .
Propriétés des classes de complexité
Fermeture
Les classes de complexité possèdent diverses propriétés de fermeture . Par exemple, les classes de décision peuvent être fermées par négation , disjonction , conjonction , voire par toutes les opérations booléennes . De plus, elles peuvent également être fermées par divers schémas de quantification. P , par exemple, est fermée par toutes les opérations booléennes et par quantification sur des domaines de taille polynomiale. Les propriétés de fermeture peuvent être utiles pour distinguer les classes ; une méthode possible pour distinguer deux classes de complexité consiste à trouver une propriété de fermeture que possède l’une des classes mais pas l’autre.
Chaque classe X qui n'est pas fermée par négation possède une classe complémentaire co-X , qui est constituée des compléments des langages contenus dans X (c'est-à-dire ). co-NP , par exemple, est une classe de complexité complémentaire importante et se trouve au centre du problème non résolu de savoir si co-NP = NP .
Closure properties are one of the key reasons many complexity classes are defined in the way that they are. Take, for example, a problem that can be solved in
O (n ^ {3}) Généralement, les réductions servent à exprimer l'idée qu'un problème est au moins aussi difficile qu'un autre. On s'intéresse donc généralement à l'utilisation d'une réduction en temps polynomial, car tout problème pouvant être efficacement réduit à un autre n'est pas plus difficile que ce dernier . Formellement, un problème est réductible en temps polynomial à un autre problème s'il existe une fonction calculable en temps polynomial telle que, pour tout , si et seulement si .
Il convient de noter que les réductions peuvent être définies de nombreuses manières différentes. Les réductions courantes sont les réductions de Cook , les réductions de Karp et les réductions de Levin , et peuvent varier en fonction des limites des ressources, telles que les réductions en temps polynomial et les réductions en espace logarithmique .
Dureté
Les réductions sont à l'origine du concept de difficulté d'un problème pour une classe de complexité donnée. Un problème est difficile pour une classe de problèmes C si tout problème de C peut être réduit en temps polynomial à . Ainsi, aucun problème de C n'est plus difficile que , puisqu'un algorithme pour permet de résoudre n'importe quel problème de C avec un ralentissement au plus polynomial. Il est particulièrement important de noter que l'ensemble des problèmes difficiles pour NP est appelé l'ensemble des problèmes NP-difficiles .
Complétude
Si un problème est difficile pour C et appartient également à C , alors on dit qu'il est complet pour C. Cela signifie qu'il s'agit du problème le plus difficile de C (puisqu'il peut exister de nombreux problèmes d'égale difficulté, plus précisément, il est aussi difficile que les problèmes les plus difficiles de C ).
La classe des problèmes NP -complets — les problèmes les plus difficiles de NP — revêt une importance particulière . Puisque tous les problèmes de NP peuvent être réduits en temps polynomial à des problèmes NP -complets, trouver un problème NP -complet qui peut être résolu en temps polynomial signifierait que P = NP .
Relations entre les classes de complexité
Le théorème de Savitch
n Théorèmes de hiérarchie
Autres modèles de calcul
Bien que les machines de Turing déterministes et non déterministes soient les modèles de calcul les plus couramment utilisés, de nombreuses classes de complexité sont définies en fonction d'autres modèles de calcul. En particulier,
- Plusieurs classes sont définies à l'aide de machines de Turing probabilistes , notamment les classes BPP , PP , RP et ZPP.
- Plusieurs classes sont définies à l'aide de systèmes de preuve interactifs , notamment les classes IP , MA et AM.
- Un certain nombre de classes sont définies à l'aide de circuits booléens , notamment les classes P/poly et leurs sous-classes NC et AC.
- Plusieurs classes sont définies à l'aide de machines de Turing quantiques , notamment les classes BQP et QMA.
Ces points sont expliqués plus en détail ci-dessous.
Calcul aléatoire
Une machine de Turing probabiliste est similaire à une machine de Turing déterministe, à ceci près qu'au lieu de suivre une seule fonction de transition (un ensemble de règles définissant la marche à suivre à chaque étape du calcul), elle sélectionne de manière probabiliste parmi plusieurs fonctions de transition à chaque étape. La définition standard d'une machine de Turing probabiliste spécifie deux fonctions de transition, de sorte que la sélection de la fonction de transition à chaque étape s'apparente à un tirage à pile ou face. L'aléatoire introduit à chaque étape du calcul introduit un risque d'erreur ; autrement dit, des chaînes que la machine de Turing est censée accepter peuvent parfois être rejetées, et inversement. Par conséquent, les classes de complexité basées sur la machine de Turing probabiliste sont définies en grande partie en fonction du taux d'erreur autorisé. Formellement, elles sont définies à l'aide d'une probabilité d'erreur . On dit qu'une machine de Turing probabiliste reconnaît un langage avec une probabilité d'erreur si :
- une chaîne de caractères dans implique que
- une chaîne de caractères qui n'est pas dans implique que
Classes de complexité importantes
Les classes fondamentales de complexité temporelle aléatoire sont ZPP , RP , co-RP , BPP et PP .
La classe la plus stricte est ZPP (temps polynomial probabiliste à erreur nulle), la classe des problèmes résolubles en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur de 0. Intuitivement, il s'agit de la classe la plus stricte de problèmes probabilistes car elle n'exige aucune erreur .
Une classe légèrement plus permissive est RP (temps polynomial randomisé), qui ne tolère aucune erreur pour les chaînes n'appartenant pas au langage, mais autorise une erreur bornée pour celles qui y appartiennent. Plus formellement, un langage appartient à RP s'il existe une machine de Turing probabiliste en temps polynomial telle que si une chaîne n'appartient pas au langage, elle la rejette systématiquement, et si elle y appartient, elle l'accepte avec une probabilité d'au moins 1/2. La classe co-RP est définie de manière similaire, à ceci près que les rôles sont inversés : aucune erreur n'est autorisée pour les chaînes du langage, mais une erreur est tolérée pour celles qui n'y appartiennent pas. Ensemble, les classes RP et co-RP englobent tous les problèmes résolubles par des machines de Turing probabilistes à erreur unilatérale .
En assouplissant davantage les conditions d'erreur pour permettre une erreur bilatérale, on obtient la classe BPP (temps polynomial probabiliste à erreur bornée), qui regroupe les problèmes résolubles en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur inférieure à 1/3 (pour les chaînes appartenant ou non au langage). La classe BPP est la plus pertinente en pratique parmi les classes de complexité probabiliste : les problèmes de cette classe admettent des algorithmes randomisés efficaces , exécutables rapidement sur des ordinateurs. La classe BPP est également au cœur du problème non résolu de l'informatique : P = BPP . Si cette hypothèse est vraie, cela signifierait que l'aléatoire n'accroît pas la puissance de calcul des ordinateurs, autrement dit, toute machine de Turing probabiliste pourrait être simulée par une machine de Turing déterministe avec un ralentissement au plus polynomial.
La classe la plus large de problèmes probabilistes solubles efficacement est PP (temps polynomial probabiliste), l'ensemble des langages solubles par une machine de Turing probabiliste en temps polynomial avec une probabilité d'erreur inférieure à 1/2 pour toutes les chaînes.
ZPP , RP et co-RP sont tous des sous-ensembles de BPP , qui est lui-même un sous-ensemble de PP . La raison en est intuitive : les classes autorisant une erreur nulle et une erreur unilatérale sont toutes incluses dans la classe autorisant une erreur bilatérale, et PP assouplit simplement la probabilité d'erreur de BPP . La relation entre ZPP , RP et co-RP est la suivante : ZPP est constitué exactement des problèmes appartenant à la fois à RP et à co-RP . Intuitivement , cela découle du fait que RP et co-RP n'autorisent qu'une erreur unilatérale : co-RP n'autorise aucune erreur pour les chaînes appartenant au langage et RP n'autorise aucune erreur pour les chaînes n'appartenant pas au langage. Par conséquent, si un problème appartient à la fois à RP et à co-RP , alors il ne peut y avoir d'erreur ni pour les chaînes appartenant au langage ni pour celles n'y appartenant pas (c'est-à-dire aucune erreur du tout), ce qui correspond précisément à la définition de ZPP .
Parmi les classes importantes de complexité spatiale aléatoire, on peut citer BPL , RL et RLP .
systèmes de preuve interactifs
Les systèmes de preuve interactifs sont des machines abstraites qui modélisent le calcul comme un échange de messages entre deux parties : un prouveur et un vérificateur . Ces parties interagissent par échange de messages, et une chaîne de caractères est acceptée par le système si le vérificateur décide de l’accepter sur la base des messages reçus du prouveur. Le prouveur dispose d’une puissance de calcul illimitée, tandis que celle du vérificateur est limitée (la définition standard des systèmes de preuve interactifs stipule que le vérificateur a une complexité polynomiale). Cependant, le prouveur n’est pas fiable (ceci empêche le système de preuve de reconnaître trivialement tous les langages en faisant déterminer au prouveur, dont la puissance de calcul est illimitée, si une chaîne appartient à un langage, puis en envoyant un « OUI » ou un « NON » fiable au vérificateur). Le vérificateur doit donc interroger le prouveur en lui posant des questions successives, et n’accepte la chaîne que s’il acquiert une forte conviction qu’elle appartient au langage.
Classes de complexité importantes
La classe NP désigne un système de preuve simple où le vérificateur est une machine de Turing déterministe à complexité polynomiale et la procédure se limite à un seul tour (le prouveur envoie au vérificateur une preuve complète unique, généralement appelée certificat ). Autrement dit, la classe NP (l'ensemble des problèmes de décision pour lesquels les instances, lorsque la réponse est « OUI », admettent des preuves vérifiables en temps polynomial par une machine de Turing déterministe) est un système de preuve où la preuve est construite par un prouveur non spécifié et où la machine de Turing déterministe joue le rôle de vérificateur. C'est pourquoi NP peut également être appelé dIP (preuve interactive déterministe), bien que cette appellation soit rarement utilisée.
Il s'avère que NP capture toute la puissance des systèmes de preuve interactifs avec vérificateurs déterministes (en temps polynomial), car on peut démontrer que pour tout système de preuve doté d'un vérificateur déterministe, un seul échange de messages entre le prouveur et le vérificateur suffit. Les systèmes de preuve interactifs offrant une puissance de calcul supérieure aux classes de complexité standard requièrent donc des vérificateurs probabilistes , ce qui signifie que les questions du vérificateur au prouveur sont calculées à l'aide d'algorithmes probabilistes . Comme indiqué dans la section précédente sur le calcul randomisé , les algorithmes probabilistes introduisent une erreur dans le système ; par conséquent, les classes de complexité basées sur les systèmes de preuve probabilistes sont définies en termes de probabilité d'erreur .
La classe de complexité la plus générale découlant de cette caractérisation est la classe IP (temps polynomial interactif), qui regroupe tous les problèmes résolubles par un système de preuve interactif , où est un système de preuve en temps polynomial probabiliste et satisfait deux propriétés : pour un langage
- (Complétude) une chaîne dans implique
- (Sonicité) une chaîne non incluse implique
Une caractéristique importante de la programmation par intégration (PI) est qu'elle est égale à PSPACE . Autrement dit, tout problème pouvant être résolu par un système de preuve interactif en temps polynomial peut également être résolu par une machine de Turing déterministe disposant de ressources spatiales polynomiales, et inversement.
Une modification du protocole IP donne naissance à une autre classe de complexité importante : AM (protocole Arthur-Merlin). Dans la définition des systèmes de preuve interactifs utilisés par IP , le prouveur ne pouvait pas voir les jetons utilisés par le vérificateur dans son calcul probabiliste ; il ne pouvait voir que les messages produits par le vérificateur avec ces jetons. C’est pourquoi ces jetons sont appelés jetons aléatoires privés . Le système de preuve interactif peut être contraint de sorte que les jetons utilisés par le vérificateur soient des jetons aléatoires publics ; autrement dit, le prouveur peut voir ces jetons. Formellement, AM est défini comme la classe des langages avec une preuve interactive dans laquelle le vérificateur envoie une chaîne aléatoire au prouveur, le prouveur répond par un message, et le vérificateur accepte ou rejette ce message en appliquant une fonction déterministe en temps polynomial. AM peut être généralisé en AM [ k ], où k est le nombre de messages échangés (ainsi, sous sa forme généralisée , AM standard défini ci-dessus est AM [2]). Cependant, il est vrai que pour tout , AM [ k ]= AM [2]. Il est également vrai que .
D'autres classes de complexité définies à l'aide de systèmes de preuve interactifs incluent MIP (temps polynomial interactif multiprover) et QIP (temps polynomial interactif quantique).
circuits booléens
Un modèle de calcul alternatif à la machine de Turing est le circuit booléen , une version simplifiée des circuits numériques utilisés dans les ordinateurs modernes . Ce modèle offre non seulement une connexion intuitive entre le calcul théorique et le calcul pratique, mais il constitue également un modèle naturel pour graphe orienté acyclique dont les arêtes représentent des fils (portant les valeurs binaires 0 et 1), les bits d'entrée sont représentés par des sommets sources (sommets sans arêtes entrantes), et tous les autres sommets représentent des portes logiques (généralement les portes ET , OU et NON ). Une porte logique est désignée comme porte de sortie et représente la fin du calcul. Le comportement entrée/sortie d'un circuit avec des variables d'entrée est représenté par la fonction booléenne ; par exemple, pour des bits d'entrée 0 et 1 , le bit de sortie du circuit est représenté mathématiquement par 0. On dit alors que le circuit calcule la fonction booléenne 0 .
Chaque circuit possède un nombre fixe de sommets d'entrée et ne peut donc traiter que des entrées de cette taille. Or, les langages (représentations formelles des problèmes de décision ) contiennent des chaînes de longueurs variables ; un seul circuit ne peut donc pas les représenter entièrement (contrairement au modèle de la machine de Turing, où un langage est entièrement décrit par une unique machine de Turing capable de traiter des entrées de toute taille). Un langage est ainsi représenté par une famille de circuits . Une famille de circuits est une liste infinie de circuits , où est un circuit à variables d'entrée. On dit qu'une famille de circuits décide d'un langage si, pour toute chaîne , appartient au langage si et seulement si , où est la longueur de . Autrement dit, une chaîne de taille appartient au langage représenté par la famille de circuits si le circuit (celui qui possède le même nombre de sommets d'entrée que le nombre de bits de ) vaut 1 lorsque est son entrée.
Alors que les classes de complexité définies à l'aide de machines de Turing sont décrites en termes de complexité temporelle , les classes de complexité de circuits sont définies en termes de taille du circuit — le nombre de sommets dans le circuit. La complexité de taille d'une famille de circuits est la fonction , où est la taille du circuit . Les classes de fonctions usuelles en découlent naturellement ; par exemple, une famille de circuits de taille polynomiale est une famille telle que la fonction est un polynôme .
Classes de complexité importantes
La classe de complexité P/poly est l'ensemble des langages décidables par des familles de circuits de taille polynomiale. Il existe un lien naturel entre la complexité des circuits et la complexité temporelle. Intuitivement, un langage à faible complexité temporelle (c'est-à-dire nécessitant relativement peu d'opérations séquentielles sur une machine de Turing) a également une faible complexité de circuits (c'est-à-dire nécessitant relativement peu d'opérations booléennes). Formellement, on peut montrer que si un langage appartient à P/poly , où f est une fonction , alors sa complexité de circuits est P/poly . Il en découle directement que P/poly = P/poly. Autrement dit, tout problème résoluble en temps polynomial par une machine de Turing déterministe peut également être résolu par une famille de circuits de taille polynomiale. De plus, l'inclusion est stricte (par exemple, certains problèmes indécidables appartiennent à P/poly ).
P/poly possède plusieurs propriétés qui la rendent très utile pour l'étude des relations entre classes de complexité. Elle est notamment précieuse pour l'étude des problèmes liés à la relation entre P et NP . Par exemple, s'il existe un langage dans NP qui n'appartient pas à P/poly , alors P/poly n'appartient pas à P/poly . P/poly est également utile pour l'étude des propriétés de la hiérarchie polynomiale . Par exemple, si NP ⊆ P/poly , alors PH se réduit à P/poly . Une description complète des relations entre P/poly et les autres classes de complexité est disponible à l'article « Importance de P/poly ». P/poly est aussi utile pour l'étude générale des propriétés des machines de Turing , car la classe peut être définie de manière équivalente comme la classe des langages reconnus par une machine de Turing en temps polynomial avec une fonction de conseil à complexité polynomiale .
Deux sous-classes de P/poly présentant des propriétés intéressantes sont NC et AC . Ces classes sont définies non seulement par la taille de leurs circuits, mais aussi par leur profondeur . La profondeur d'un circuit correspond à la longueur du plus long chemin orienté reliant un nœud d'entrée à un nœud de sortie. La classe NC regroupe les langages résolubles par des familles de circuits dont la taille est polynomiale et la profondeur polylogarithmique. La classe AC est définie de manière similaire à NC , à la différence que les portes logiques peuvent avoir un nombre d'entrées illimité (les portes ET et OU peuvent donc être appliquées à plus de deux bits). La classe NC est remarquable car elle peut être définie comme la classe des langages possédant des algorithmes parallèles efficaces .
Calcul quantique
et:
Autres types de problèmes
Bien que la plupart des classes de complexité étudiées par les informaticiens soient des ensembles de problèmes de décision , il existe également des classes de complexité définies à partir d'autres types de problèmes. On trouve notamment des classes de complexité constituées de problèmes de dénombrement , de problèmes de fonctions et de problèmes de promesses . Celles-ci sont expliquées plus en détail ci-dessous.
Problèmes de dénombrement
Problèmes de fonctionnement
Problèmes de promesse
Résumé des relations entre les classes de complexité
Le tableau suivant présente quelques classes de problèmes étudiées en théorie de la complexité. Si X est un sous-ensemble strict de Y , X est représenté sous Y par un trait foncé. Si X est un sous-ensemble de Y, mais que l'égalité de X et Y est incertaine, le trait est plus clair et en pointillés. Techniquement, la distinction entre décidable et indécidable relève davantage de la théorie de la calculabilité , mais elle permet de mieux appréhender les classes de complexité.
