ein Bool'scher Ausdruck
in konjunktiver Normalform. Gibt es einen Wert für 
, sodass es für alle Werte
einen Wert für 
gibt, sodass für alle ...sodass = wahr ?
Also: Gibt es eine Wahrheitszuweisung für 
, für die
Darstellung eines Kapitels aus dem Buch ECOMPUTATIONAL COMPLEXITY von Christos H. Papadimitriou
herausgegeben 1994, Addison Wesley company
Vortragender: Franz Zoister
Datum: 13.12.1997
PSPACE steht für polynomial space. Die Klasse der Probleme, die mit polynomiellem Platzverbrauch lösbar sind. Nicht in Betracht gezogen wird hierbei die Komplexität der Zeit.
Die Suche nach der Antwort auf die folgende Frage: Sei ein Bool'scher Ausdruck
in konjunktiver Normalform. Gibt es einen Wert für , sodass es für alle Werte
einen Wert für gibt, sodass für alle ...sodass = wahr ?
Also: Gibt es eine Wahrheitszuweisung für , für die
Dieses Problem liegt in PSPACE. Es ist sogar PSPACE complete: Jede endliche Turing-Maschine kann in der Form von QSAT beschrieben werden.
Nun kann man andere Probleme betrachten, und sie mit QSAT vergleichen. Es stellt sich heraus, dass auf den ersten Blick relativ einfache anmutende Probleme ebenfalls PSPACE complete sind.
Die Regeln: Spieler A beginnt das Spiel mit der Nennung des Namens einer Stadt. (z. B. `WIEN'), Spieler B nennt dann eine Stadt, deren Name mit dem letzten Buchstaben der vorher genannten Stadt beginnt (z. B. `WASHINGTON'), Spieler A setzt dann wiederum fort (z. B. `KIEW') usw. Eine Stadt, die bereits genannt wurde kann nicht wieder in der Kette vorkommen. In diesem Beispiel kann nach `KIEW' nicht `WIEN' angegeben werden, da es bereits im Spiel vorgekommen ist. Der Spieler, der (am Zug befindlich) keine Stadt nennen kann, weil alle Namen mit dem entsprechenden Anfangsbuchstaben aufgebraucht sind, hat verloren.
Der Spielbaum von Geography kann mit polynomiellem Platzaufwand gelöst werden. Es kann aber auch gezeigt werden, dass es PSPACE-complete ist. Man kann für ein beliebiges QSAT-Problem ein Geography-Problem konstruhieren, das das QSAT-Problem entscheidet. (mit Reduktionsfunktions-Komplexität in logSPACE)
Von einer eingeschränkte Version von Go kann nach einem analogen Schema ebenfalls gezeigt werden, dass es PSPACE-complete ist. Hier werden durch verschiedene Spiel-Positionen die Knoten des Goegraphy-Spiels `simuliert'.
Nicht nur in Spielen und logischen Gleichungen, sondern auch in durchaus praktischen
Aufgabenstellungen können PSPACE-complete - Probleme eine Rolle spielen.
Spieler muss nicht unbedingt ein seine Zuege optimierender Gegner sein. Seine `Zuege' können durchaus auch zufällig oder durch einen stochastischen Prozess zustande kommen.
Stochastic satisfiability SSAT:
Diese Gleichung 
zeigt einen interaktiven stochastischen Prozess, nicht einen fixen existierenden Suchbaum.
Die beste Antwort des Gegners kann nicht berechnet werden, weil sie `zufällig' gewählt
wird. Das Problem liegt hier in der Optimierung der Wahrscheinlichkeit, zu gewinnen.
Objwohl also der Gegner nicht den `besten Zug' macht, stellt sich dennoch heraus, dassdieses Problem genauso hart wit QSAT ist.
Ein Beispiel für diese Art von Problemen ist ein stochastisches scheduling-Problem, bei welchem Prozesse auf zwei Prozessoren, so eingeplant werden müssen, dass sich eine möglichst effiziente Auslastung ergibt. Die Prozesse sind untereinander abhängig (manche können nur starten, wenn andere bereits beendet sind - Dies ist mit einem gerichteten Graphen darstellbar) und haben unterschiedliche nicht nicht vorher bekannte (statistisch modellierte) Laufzeit.
Es gibt natürlich eine ganze Menge mehr untersuchter Probleme, welche in der
PSPACE-complete-Klasse wiederzufinden.
Hier sei weiterfuehrende Literatur angegeben:
theoret. PSPACE
(GEOGRAPHY)
This document was generated using the LaTeX2HTML translator Version 96.1-e (April 9, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 n-zoister.
The translation was initiated by Wolfgang Slany on Fri Jan 9 19:10:13 MET 1998