NTIME
From Wikipedia, the free encyclopedia
En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non déterministe.
Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être résolus en temps par une machine de Turing non déterministe.
La classe NP des problèmes de décision décidables par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée peut être définie comme :
De même, la classe NEXPTIME des problèmes de décision décidable par une machine de Turing non déterministe en temps exponentiel est définie comme :
