Diskussion:Platzkomplexität

Ich habe diesen Artikel angelegt, um das Thema Komplexität mal ein bisschen zu strukturieren. Leider fehlen mir gerade noch ein paar Informationen, um den Artikel weiter auszubauen (ist schon etwas her dass ich die Prüfung bestanden habe):

• Sind Turingmaschinen bezüglich der Platzkomplexität equivalent zu Registermaschinen? Gibt es maschinenmodelle, für die das nicht zutrifft?
• Was sind dich wichtigsten Komplexitätsklassen bezüglich der Platzkomplexität? Was sind genau die Eigenschaften von linear beschränkten Turingmaschienen? Waren die nicht äquivalent zu irgend einer Sprachfamilie?

kennt sich da jemand aus? -- D. Düsentrieb ⇌ 19:28, 11. Okt 2004 (CEST)

Platzkomplexität (ich hätte Raumkomplexität gesagt) macht bei Registermaschinen zumindest im Sinne von Anzahl der benutzten Register keinen Sinn, wenn ein Register beliebig große Zahlen enthalten kann, da dann eine konstante Zahl von Registern ausreicht.

Eine linear beschränkte Turingmaschine arbeitet nur auf ihrer Eingabe und erkennt eine kontextsensitive Sprache. Zu erkennen, ob ein geg. Wort von einer geg. lin. beschr. TM akzeptiert wird, ist ein PSPACE-vollständiges Problem. Andere wichtige Platzkomplexitäten, die alle schon Artikel haben, sind L und NL. -- Tian 17:26, 4. Mär 2005 (CET)

Habe mal eine kleine Übersicht über Platzkomplexitätsklassen eingefügt. Wer genauere Sachverhalte kennt (Namen von Beweisen oder sogar Beweisskizzen (verständliche)) kann gerne noch mehr dazu schreiben. Das Thema ist wichtiger als man meint... Mathias 11:20, 2. Feb 2006 (CET)

Im Artikel fehlen Links/die Erwähnung von 'In-Place-Algorithmus' und 'Out-Of-Place-Algorithmus'. --arilou (Diskussion) 09:17, 27. Nov. 2020 (CET)Beantworten