Lexikon der Mathematik: LBA-Problem
das Problem, ob die Komplexitätsklassen DSPACE(n) und NSPACE(n) übereinstimmen.
Der Name beruht darauf, daß eine linear platzbeschränkte Turing-Maschine früher als Linear Bounded Automaton (LBA) bezeichnet wurde.
Die Bedeutung des Problems liegt darin, daß NSPACE(n) die Klasse der kontextsensitiven Sprachen ist. Bisher ist mit dem Satz von Savitch (Savitch, Satz von) nur bekannt, daß NSPACE(n) in DSPACE(n2) enthalten ist.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!