NL-Vollständigkeit
Einfache Sprache
- Analog wie NP-Vollständigkeit. Wichtig ist, dass wir keine Polynomialzeitreduktion benutzen können, da jedes Problem in NL in Polynomialzeit lösbar sind. Also Satz NL teil von P.
Def. NL-Vollständigkeit
Eine Sprache $L_0$ heißt NL-vollständig g.d.w. $L_0\in \mathbf{NL}$ und $\forall L\in \mathbf{NL}$ gilt: $L\leq_\mathrm{L} L_0$ .
Hier wird also die Log-Raum-Reduktion genutzt.