Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 1 von 1 Treffern
Autor Beitrag
Thema: Zeitkomplexität/ Platzkomplexität Aufgabe
very_humble_guy

Antworten: 0
Hits: 497
Zeitkomplexität/ Platzkomplexität Aufgabe 08.02.2021 00:09 Forum: Berechenbarkeits- und Komplexitätstheorie


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
Zeige Beiträge 1 bis 1 von 1 Treffern