Citation Hunt

Bestenliste

Das unten stehende Wikipedia-Snippet wird von keiner verlässlichen Quelle unterstützt. Kannst du eine finden?

Klicke auf Verstanden!, um zu Wikipedia zu gehen und das Snippet zu reparieren, oder Nächstes!, um ein anderes zu sehen. Viel Glück!

In Seite 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 ′ {\displaystyle L'} auf eine andere Sprache L {\displaystyle L} mittels einer Funktion f {\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 A ′ ≤ l o g A {\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.