| Der letzte Beitrag |
| very_humble_guy |
Zeitkomplexität/ Platzkomplexität Aufgabe
Hallöchen,
ich hätte eine Frage bezüglich einer Aufgabe, bei der ich nicht mehr weiter komme. Undzwar soll ich folgendes zeigen:
a) DTIME(n^3) Teilmenge von NL => DTIME(n^6)) Teilmenge von NL
b) NL != DTIME(n^3)
NL ist hierbei so definiert: NL = NSPACE(log(n))
Bei der a) habe ich das so gelöst: DTIME(n^6) = DTIME(n^(3*2)) = DTIME(n^3 * n^2) = DTIME(n^3) * DTIME(n^2) .
Da wir wissen, dass DTIME(n^3) in NL liegt und das DTIME(n^2) kleiner ist als DTIME(n^3), liegt auch dies in NL.
Zudem könnte man ja sagen, dass man jedes n^6 aus n^3 darstellen kann (durch 2* n^3). Wenn es also ein n^3 gibt, welches in NL liegt, dann gibt es auch ein n^6, welches in NL liegt, da es ja dasselbe ist wie 2*n^3
Ich weiß zwar, dass NSPACE(log(n)) (also NL) nicht = DTIME(n^3) ist, aber wie genau kann ich sowas denn zeigen?
Wenn mir da jemand weiter helfen könnte, wäre ich euch mega dankbar!
LG,
very_humble_guy |
|
|
