Logarithmische Reduktion

Logarithmische Reduktion

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

Neben der Forderung, dass eine Sprache L' auf eine andere Sprache L mittels einer Funktion 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 A' \le_{log} A verwendet.

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • LOGSPACE-Reduktion — Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion. Neben der Forderung, dass eine Sprache L auf eine andere Sprache L mittels einer Funktion reduzierbar ist, muss… …   Deutsch Wikipedia

  • Logarithmisch platzbeschränkte Reduktion — Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion. Neben der Forderung, dass eine Sprache L auf eine andere Sprache L mittels einer Funktion reduzierbar ist, muss… …   Deutsch Wikipedia

  • Barometrische Hoehenformel — Durchschnittlicher Druck und Dichte in Abhängigkeit von der Höhe.Logarithmische Darstellung für große Höhen …   Deutsch Wikipedia

  • Höhenformel — Durchschnittlicher Druck und Dichte in Abhängigkeit von der Höhe.Logarithmische Darstellung für große Höhen …   Deutsch Wikipedia

  • E-Funktion — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

  • E Funktion — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

  • Exponential — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

  • Exponentialfunktionen — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

  • Exponentialreihe — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

  • Natürliche Exponentialfunktion — Die Mathematik bezeichnet als Exponentialfunktion eine Funktion der Form mit der Basis . In der gebräuchlichsten Form sind dabei für den Exponenten x die reellen Zahlen zugelassen. Im Gegensatz zu den Potenzfunktionen, bei denen die Basis die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”