Direkt zum Inhalt

Lexikon der Mathematik: Logspace-Reduktion

Begriff aus der Komplexitätstheorie.

Eine Sprache L1 (bzw. ein Entscheidungsproblem) ist auf eine Sprache L2 Logspace-reduzierbar, Notation L1logL2, wenn es eine von einer Turing-Maschine mit ⌈ld(n)⌉ Zellen auf dem Arbeitsband berechenbare Transformation f gibt, die Wörter über dem Alphabet von L1 in Wörter über dem Alphabet von L2 so überführt, daß gilt: \begin{eqnarray}w\in {L}_{1}\iff f(w)\in {L}_{2}.\end{eqnarray}

Logspace-Reduktionen spielen für die Raumkomplexität diejenige Rolle, die polynomielle Zeitreduktionen in der Theorie der NP-Vollständigkeit spielen.

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