NL-Schwere

Einfache Sprache

Analog zu NP-Schwer. NL-schwer ist die Eigenschaft eines Problems, mindestens so schwer lösbar zu sein wie alle Probleme aus NL. Für alle Probleme aus NL muss es also eine Log-Raum-Reduktion geben, welche es in die Sprache des NP-schweren Problem umwandelt.

Def. NL-Schwere

Eine Sprache $L_0$ heißt NL-schwer, g.d.w.

$$\forall L \in \mathbf{NL} : L \leq_\mathrm{L} L_0\;.$$