Complexidade NL

Na teoria da complexidade, NL (espaço-logarítmico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística, usando uma quantidade de espaço de memória logarítmica. NL é uma generalização de L, a classe dos problemas de espaço logarítmico em uma máquina de Turing determinística. Desde que qualquer máquina de Turing seja também uma máquina de Turing não-determinística, nós temos que L está contida em NL. NL pode ser formalmente definida em termos de recursos computacionais de espaço não-determinístico (ou NSPACE) como NL = NSPACE(log n). Importantes resultados em teoria da complexidade nos permitem relacionar esta classe de complexidade com outras classes, dizendo-nos algo sobre o poder relativo dos recursos envolvidos. Resultados na área de algoritmos, por outro lado, nos informam quais problemas podem ser resolvidos com este recurso. Infelizmente, como grande parte da teoria da complexidade, muitas questões importantes sobre NL ainda estão abertas. Ocasionalmente, NL é referida como RL devido a sua definição probabilística abaixo. No entanto, esse nome é mais frequentemente usado para referir espaços logarítmicos aleatórios, o qual não é conhecido como sendo NL. O "mais difícil" ou "mais expressivo" problema na classe de complexidade são problemas que são completos para aquela classe.