Article · Deutsch
In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch Platz entschieden werden können,wobei ein beliebiges Polynom ist. Betrachtet man nicht-deterministische Turingmaschinen, so erhält man die Klasse NEXPSPACE.Nach dem Satz von Savitch gilt EXPSPACE = NEXPSPACE. In der DSPACE / NSPACE-Notation ausgedrückt gilt also:
Abstract from DBpedia / Wikipedia · CC BY-SA