Complexidade NL: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Migrating interwiki links, now provided by Wikidata on d:q12857599 |
m ortografia, concordância verbal |
||
Linha 5:
Na teoria da complexidade, '''NL''' (espaço-logarítimico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina deTuring 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
'''NL''' pode ser formalmente definida em termos de recursos computacionais de espaço não-determinístico (ou NSPACE) como '''NL''' = '''NSPACE'''(log n).
Linha 51:
Para mostrar que '''NL''' está contida em C, nós simplesmente tomamos um algoritmo '''NL''' e escolhemos um caminho de computação aleatório de tamanho n, fazendo isso 2n vezes. Devido a nenhum caminho de computação exceder tamanho n, e existirem 2n caminhos de computação em todos, temos uma boa chance de atingir a aceitação (limitada inferiormente por uma constante).
O único problema é que nós não temos espaço no espaço-
Assim, quando olharmos apenas para o espaço por si só, parece que aleatoriedade e não-determinismo são igualmente poderosos.
| |||