Log-Raum-Reduktion
Einfache Sprache
Def. Log-Raum-Reduktion
Eine Sprache $A$ ist Log-Raum reduzierbar zu einer Sprache $B$, geschrieben $A\leq_\mathrm{L} B$ fall es eine Logarithmische Platzkomplexität berechenbare Funktion $f:\Sigma^*\to\Sigma^*$ existiert so, dass für alle $w$ gilt
$$w\in A\iff f(w)\in B\;.$$Die Funktion $f$ wird auch Log-Raum Reduktion von $A$ nach $B$ genannt.