Direkt zum Inhalt

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte