NL (Komplexitätsklasse)

In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können.

NL ist eine Erweiterung der Klasse L, die analog für deterministische Turingmaschinen definiert ist.

Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.