Logarithmisch platzbeschränkte Reduktion
- 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 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 
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:
Reduktion (Theoretische Informatik) — Die Reduktion ist eine Methode der Theoretischen Informatik. Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen.… … Deutsch Wikipedia
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
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 reduzierbar ist, muss… … Deutsch Wikipedia
Turingreduktion — Die Reduktion ist eine Methode der Theoretischen Informatik. Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen.… … Deutsch Wikipedia
Satz von Shamir — In der theoretischen Informatik ist Vollständigkeit eine Eigenschaft von Problemen in Bezug auf eine Komplexitätsklasse. Intuitiv ist ein Problem dann vollständig für eine bestimmte Komplexitätsklasse, wenn kein anderes Problem der Klasse… … Deutsch Wikipedia
Vollständigkeit (Komplexitätstheorie) — In der theoretischen Informatik ist Vollständigkeit eine Eigenschaft von Problemen in Bezug auf eine Komplexitätsklasse. Intuitiv ist ein Problem dann vollständig für eine bestimmte Komplexitätsklasse, wenn kein anderes Problem der Klasse… … Deutsch Wikipedia
Kontextfrei — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst. Als Kontextfreie Sprache ( … Deutsch Wikipedia
LOGCFL — In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme die mit logarithmischen Speicheraufwand auf eine kontextfreie Sprache (engl. Context Free Language) reduziert werden können. Inhaltsverzeichnis 1… … Deutsch Wikipedia
