---

Geschrieben von very_humble_guy am 08.02.2021 um 00:09:

  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