Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Zeitkomplexität / Platzkomplexität
Autor
Universität/Hochschule Zeitkomplexität / Platzkomplexität
CoolerTyp
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2021
Mitteilungen: 1
  Themenstart: 2021-02-07

Hallöchen, ich habe hier ein paar Aufgaben bezüglich der Komplexität (Zeit und Platz) an denen ich verzweifle. In unserem Skript gibt es garkeine Beispiele wie man sowas angeht und ich finde durch Googlen auch keine Hinweise oder Lösungen, wie man sowas angeht. Deshalb wollte ich hier nachfragen, ob mir jemand mit den folgenden Aufgaben weiter helfen kann: Aufgabe: Sind diese folgenden Aussagen wahr oder falsch? Kurze Begründung angeben: a) [DTIME($\mathcal{O}$(n)) = NTIME($\mathcal{O}$(n))] ⇒ [DTIME($\mathcal{O}$($2^n$)) = NTIME($\mathcal{O}$($2^n$))] b) NTIME($\mathcal{O}$(n)) = PSPACE c) NSPACE(n^(5/2)) ⊊ DSPACE(n^(11/2)) Bei der c) dachte ich mir, dass man ja eine Maschine M, die DSPACE berechnet, auch als eine Maschine sehen kann, die in NSPACE liegt, aber ihren Nichtdeterminismus nicht ausnutzt. Daher könnte man das DSPACE in ein NSPACE umschreiben. Somit würde die Aussage wahr werden, da die linke Seite weniger Platz benötigt als die rechte. Bei der b) dachte ich mir, dass die Aussage wahr ist, weil ja O(n) in linearer Zeit berechnet wird und PSPACE ja polynomielle Zeit braucht. Bei der a) habe ich Überhaupt keine Ahnung und würde mich über Hilfe riesig freuen :D LG, CoolerTyp


   Profil
CoolerTyp wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]