Kann FPSPACE exponentiell lange Ausgaben liefern?

7

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)?

Unendlich neugierig
quelle

Antworten:

7

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 EingabenX1Xn.

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

David Richerby
quelle
PSPACE ist ein Entscheidungsproblem. Sollte die Ausgabe also nicht nur Ja / Nein sein und daher eine konstante Größe haben?
Tom Cornebize
@ TomCornebize Die Frage bezieht sich auf F PSPACE, eine Klasse von Funktionsproblemen. (Obwohl ich vielleicht auch "FLOGSPACE" hätte sagen sollen. Allerdings sprechen alle eher von "LOGSPACE-Reduzierungen" als von "FLOGSPACE".)
David Richerby
Ich denke, das ist wahrscheinlich, weil FLOGSPACE ein bisschen zu nah an einem ... ähm ... Club nur für Spezialisten klingt.
Luke Mathieson