Lexikon der Mathematik: Logspace-Reduktion
Begriff aus der Komplexitätstheorie.
Eine Sprache L1 (bzw. ein Entscheidungsproblem) ist auf eine Sprache L2 Logspace-reduzierbar, Notation L1 ≤logL2, 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:
Logspace-Reduktionen spielen für die Raumkomplexität diejenige Rolle, die polynomielle Zeitreduktionen in der Theorie der NP-Vollständigkeit spielen.
Schreiben Sie uns!