Ich kann mit einigen Sachen nicht klar kommen. Warum ist DTIME(f)eine Teilmenge von DSpace(f) und
PSpace eine Teilmenge von NPSpace?

PSpace eine Teilmenge von NPSpace?

Hier helfe ich mal aus, das ist das einfachste [img]http://www.fb18.de/gfx/15.gif[/img] In PSpace sind die Sprachen, die von einer DTM in polynomieller Zeit entschieden weredn können, in NPSpace die von einer NTM. Nun ist jede DTM insbesondere auch eine NTM, zumindest lässt sie sich trival umformen. Es schreibt ja keiner vor, dass bei einer NTM mal etwas uneindeutiges sein _muss_.
Also kannst du jedes Problem, was mit einer DTM schon in polynomieller Zeit erledigbar ist, auch von einer NTM ganz problemlos lösen lassen, sprich PSpace teilmenge NPSpace

Warum ist DTIME(f)eine Teilmenge von DSpace(f)

Für 1-Band-TMs ist das recht einfach: Wenn die TM auf einer Eingabe der Länge n nur f(n) Schritte macht, kann sie dabei höchstens f(n) Felder besuchen. Damit ist sie f(n)-platzbeschränkt.

Bei k-Band-TMs geht das über die Bandkompression. Mit obiger Überlegung ist die f(n)-zeitbeschränkte k-Band TM erstmal k*f(n)-platzbeschränkt, weil man in einem Rechenschritt höchstens k Felder besuchen kann (das ist der "schlimmste" Fall: man muss dafür alle Köpfe jeweils auf einen unbesuchten Platz bewegen). Dann komprimiert man das Band nach Theorem 8.5 (man setzt c=1/k). Und hat eine f(n)-platzbeschränkte k-Band-TM.

Damit sind also alle Sprachen, die man f(n)-zeitbeschränkt akzeptieren kann, auch f(n)-platzbeschränkt akzeptierbar.