Posted by Andreas on January 26, 2001 at 22:47:22:
Hallo,
in der letzten Uebungsstunde haben wir festgestellt, dass TO die Klasse SGT (=CPSR) enthaelt, falls die Zeitstempelordnung beliebig ist (der Beweis mit der topologischen Sortierung). Auf einem aelteren Uebungsblatt kam einmal vor, dass 2PL und TO nicht vergleichbar sind. Das heisst doch, dass es S gibt, die ausserhalb von TO, aber in 2PL sind, und weil TO > CPSR, dann auch ausserhalb von CPSR sind??
(Oder kann man sagen, dass bei beliebig waehlbarer Zeitstempelordnung TO die Klasse 2PL enthaelt? Ist TO mit solcher beliebig waehlbaren Zeitstempelordnung so maechtig wie VSR (es ist ja dann auch in NP, oder?)
Ich habe mal eine Zeichnung angefertigt fuer die erwaehnten Klassen, links fuer den Fall TO mit fixer Zeitstempelordnung, rechts mit anpassbarer - stimmt die?
Merci,
Andreas