Logarithmisch platzbeschränkte Reduktion

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion.

Neben der Forderung, dass eine Sprache ${\displaystyle L'}$ auf eine andere Sprache ${\displaystyle L}$ mittels einer Funktion ${\displaystyle f\;}$ reduzierbar ist, muss diese Funktion für eine logarithmische Reduktion zusätzlich auf logarithmischem Platz berechnet werden können.

Logarithmische Reduktionen werden in der Komplexitätstheorie üblicherweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NL auch NL-vollständig ist.

Als Schreibweise wird hierbei häufig ${\displaystyle A'\leq _{log}A}$ verwendet.

Man beachte, dass für diese Reduktion die Transitivität gezeigt werden kann. Nur dadurch kann man mit diesem Begriff arbeiten.