PSPACE

Einfache Sprache

Def. PSPACE

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

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

Sätze

• Satz PSPACE gleich NPSPACE
• Satz P Teilmenge von PSPACE
• Satz PSPACE Teilmenge von EXPTIME