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
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.