Diko : NL

NL

Catégories

Nom

Informations lexicales

Langue:français, Morpho:nospace, Morpho:withmaj, Sigle:

Informations sémantiques

⫙, [polit] , source:wiki

Variantes

›

nl

‹

nl

Définitions

Nouvelle lune (phase où la lune est invisible).

1. Un problème A est NL-dur si tout problème de NL se réduit en espace logarithmique à A. Un problème est NL-complet s'il est dans NL et NL-dur.

2. En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité. Cette classe est aussi appelée NLogSpace [réf. nécessaire]. C'est l'ensemble des problèmes de décision qui peuvent être décidés par des machines de Turing non déterministes dont l'espace de travail est borné par une fonction logarithmique.

Liens externes

›

dbnary:1-NL-nom

Un raffinement sémantique

›

NL

(complexité)