Kann FPSPACE exponentiell lange Ausgaben liefern?

Ich kann diese Frage nicht kommentieren , daher stelle ich sie hier als neue Frage:

Ricky Demer gibt dort in einem Kommentar zur ersten Antwort an

"[...] da FPSPACE exponentiell lange [...] Ausgänge liefern kann"

Wie kann das sein? Wie kann ein Algorithmus in FSPACE eine exponentiell lange Ausgabe liefern? Bedeutet dies, dass wir den Ausgaberaum in der Definition von FSPACE nicht zählen (im Gegensatz zu dem, was ich bisher geglaubt habe)?

Raumklassen enthalten immer nur Arbeitsraum: Das Modell besteht darin, dass wir ein schreibgeschütztes Eingabeband und ein schreibgeschütztes Ausgabeband sowie ein schreibgeschütztes Arbeitsband (oder mehrere solcher Bänder) haben, auf denen wir nur ein verwenden dürfen begrenzte Menge an Platz. Diese Definition ist notwendig, damit etwas wie LOGSPACE Sinn ergibt: Wenn Sie die Ausgabe als Teil des verwendeten Speicherplatzes gezählt haben, würde selbst ein Algorithmus wie "nur die Eingabe ausgeben" in LOGSPACE nicht ausgeführt. Dies ist wichtig, da wir häufig LOGSPACE-Reduzierungen zwischen Problemen verwenden möchten.

Ein einfaches Beispiel für einen (nicht trivialen) FPSPACE-Algorithmus, der exponentiell viel Ausgabe erzeugt, ist ein SAT-Löser, der nur jede mögliche Wertekombination für die Variablen ausprobiert und die Kombinationen ausgibt, die der Formel entsprechen. Dies erzeugt eine exponentiell lange Ausgabe für die Klasse von Eingaben$X_1\lor\dots\lor X_n$.

Beachten Sie, dass wir für zeitgebundene Komplexitätsklassen keine derartigen Probleme haben, da auf einer Turing-Maschine geschrieben wird $\ell$ Ausgabesymbole brauchen immer mindestens $\ell$ Zeitschritte so, zum Beispiel ein Polynom Zeit Maschine nur polynomial viel Leistung produzieren kann.