TEMPS D'EXP. - EXPTIME

Dans la théorie de la complexité computationnelle , la classe de complexité EXPTIME (parfois appelée EXP ou DEXPTIME ) est l' ensemble de tous les problèmes de décision qui peuvent être résolus par une machine de Turing déterministe en temps exponentiel , c'est-à-dire en temps O (2 ^{p ( n )} ) , où p ( n ) est une fonction polynomiale de n .

EXPTIME est une classe intuitive dans une hiérarchie exponentielle de classes de complexité avec des oracles ou des alternances de quantificateurs de plus en plus complexes. Par exemple, la classe 2-EXPTIME est définie de manière similaire à EXPTIME mais avec une limite temporelle doublement exponentielle . Cela peut être généralisé à des limites de temps de plus en plus élevées. ${\textstyle 2^{2^{p(n)}}}$

EXPTIME peut également être reformulé en tant que classe spatiale APSPACE, l'ensemble de tous les problèmes pouvant être résolus par une machine de Turing alternative dans un espace polynomial.

EXPTIME concerne les autres classes de complexité de temps de base et de l' espace de la façon suivante: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . De plus, par le théorème de la hiérarchie temporelle et le théorème de la hiérarchie spatiale , on sait que P EXPTIME, NP NEXPTIME et PSPACE EXPSPACE.

Définition formelle

En termes de DTIME ,

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}$

Relations avec les autres classes

Il est connu que

et aussi, par le théorème de la hiérarchie temporelle et le théorème de la hiérarchie spatiale , que

Dans les expressions ci-dessus, le symbole signifie "est un sous-ensemble de", et le symbole signifie "est un sous-ensemble strict de".

donc au moins une des trois premières inclusions et au moins une des trois dernières inclusions doivent être propres, mais on ne sait pas lesquelles sont. La plupart des experts pensent que toutes les inclusions sont appropriées. On sait aussi que si P = NP , alors EXPTIME = NEXPTIME , la classe de problèmes résolvables en temps exponentiel par une machine de Turing non déterministe . Plus précisément, EXPTIME NEXPTIME si et seulement s'il existe des langages creux dans NP qui ne sont pas dans P .

EXPTIME peut être reformulé comme la classe spatiale APSPACE, l'ensemble de tous les problèmes qui peuvent être résolus par une machine de Turing alternative dans l'espace polynomial. C'est une façon de voir que PSPACE EXPTIME, puisqu'une machine de Turing alternative est au moins aussi puissante qu'une machine de Turing déterministe.

EXPTIME-complet

Un problème de décision est EXPTIME-complet s'il est dans EXPTIME et chaque problème dans EXPTIME a une réduction à plusieurs uns en temps polynomial . En d'autres termes, il existe un algorithme en temps polynomial qui transforme les instances de l'un en instances de l'autre avec la même réponse. Les problèmes qui sont EXPTIME-complets peuvent être considérés comme les problèmes les plus difficiles dans EXPTIME. Notez que bien que l'on ne sache pas si NP est égal à P, nous savons que les problèmes EXPTIME-complets ne sont pas dans P ; il a été prouvé que ces problèmes ne peuvent pas être résolus en temps polynomial , par le théorème de la hiérarchie temporelle .

Dans la théorie de la calculabilité , l'un des problèmes indécidables de base est le problème de l' arrêt : décider si une machine de Turing déterministe (MNT) s'arrête. L'un des problèmes les plus fondamentaux d'EXPTIME-complet est une version plus simple de ceci, qui demande si un DTM s'arrête dans au plus k étapes. C'est dans EXPTIME car une simulation triviale nécessite un temps O( k ), et l'entrée k est codée en utilisant O(log k ) bits, ce qui provoque un nombre exponentiel de simulations. Il est EXPTIME-complet parce que, grosso modo, nous pouvons l'utiliser pour déterminer si une machine résolvant un problème EXPTIME accepte en un nombre exponentiel d'étapes ; il n'en utilisera pas plus. Le même problème avec le nombre d'étapes écrites en unaire est P-complet .

D'autres exemples de problèmes EXPTIME-complete incluent le problème d'évaluation d'une position dans les échecs généralisés , les dames ou le Go (avec les règles japonaises de ko). Ces jeux ont une chance d'être terminés par EXPTIME car les jeux peuvent durer un nombre de coups exponentiel par rapport à la taille du plateau. Dans l'exemple de Go, la règle japonaise du ko est suffisamment intraitable pour impliquer une EXPTIME-complétude, mais on ne sait pas si les règles américaines ou chinoises les plus faciles à appliquer pour le jeu sont EXPTIME-complete.

En revanche, les jeux généralisés qui peuvent durer un certain nombre de coups polynomiaux dans la taille du plateau sont souvent PSPACE-complet . Il en va de même pour les jeux exponentiellement longs dans lesquels la non-répétition est automatique.

Un autre ensemble de problèmes EXPTIME-complet importants concerne les circuits succincts . Les circuits succincts sont des machines simples utilisées pour décrire certains graphiques dans un espace exponentiellement moins grand. Ils acceptent deux nombres de sommets en entrée et en sortie s'il y a une arête entre eux. Pour de nombreux problèmes de graphes P-complets naturels , où le graphe est exprimé dans une représentation naturelle telle qu'une matrice d'adjacence , résoudre le même problème sur une représentation de circuit succincte est EXPTIME-complet, car l'entrée est exponentiellement plus petite ; mais cela nécessite une preuve non triviale, puisque des circuits succincts ne peuvent décrire qu'une sous-classe de graphes.

Les références