Zeitkomplexität/ Platzkomplexität Aufgabe |
08.02.2021, 00:09 | Auf diesen Beitrag antworten » |
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 |
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|