Informatik

Was ist die Komplexitätsklasse NL?

$NL$ enthält Entscheidungsprobleme, die nichtdeterministisch mit logarithmischem Speicher lösbar sind.

Klassisches vollständiges Problem: Erreichbarkeit in gerichteten Graphen.