Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Platzkonstruierbar/zeitkonstruierbar
Wir haben damals bei der zeitkonstruierbarkeit einer Funktion f aufgeschrieben,dass es eine det TM gibt die für eine Eingabe der Länge n bin(f(n)) in Zeit O(f(n)) berechnet. Bei der Platzkonstruierbarbeit haben wir aber aufgeschrieben, wenn es eine det TM gibt die für Eingabe der Länge n f(n) berechnet und nicht bin(f(n)). Im Internet gibt es dazu Definitionen die einmal auch von bin(f(n)) sprechen und Definitionen die von f(n) sprechen (ANalog gibt es Definitionen die bei der zeitkonstruierbarkeit von f(n) und andere die von bin(f(n)) sprechen). Was ist hier denn jetzt eigentlich richtig oder haben wir das nur falsch aufgeschrieben?
Zumindest hast du dich nicht verschrieben, ich habe das Gleiche.
Ich schätze mal, da gehört noch ein bin hin…
Sollte eigentlich bin(f(n)) sein, zumindest bin ich mir da ziemlich sicher bei der Zeitkonstruierbarkeit. Bei der Platzkonstruierbarkeit denke ich auch auch, dass es bin(f(n)) ist, da, so wie ich es bis jetzt in Büchern gesehen habe, immer darauf bezogen wird. Wird wohl dann auch einfacher im Bezug zu logspace sein.