NSPACE

En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe.

Plus précisément, ${\displaystyle {\mathsf {NSPACE}}(f(n))}$ est la classe des problèmes de décision qui, pour une entrée de taille ${\displaystyle n}$, peuvent être décidés par une machine de Turing non déterministe fonctionnant en espace ${\displaystyle {\mathcal {O}}(f(n))}$.