NPSPACE

Einfache Sprache

Def. NPSPACE

$\mathbf{PSPACE}$ ist die Klasse der Sprachen, die durch eine Nichtdeterministische Turingmaschine in Polynomialzeit entscheidbar sind. Also

$$\mathbf{NPSPACE} = \bigcup_k\mathbf{SPACE}(n^k)\;.$$

• Satz PSPACE gleich NPSPACE