Also known as NLOGSPACE, Nondeterministic Logarithmic-space
classe di complessità
Article · Italiano
La classe NL (abbreviazione di nondeterministic logarithmic space, ovvero "spazio logaritmico non deterministico", nota anche come NLOGSPACE) è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con . Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che .
Abstract from DBpedia / Wikipedia · CC BY-SA