Clases L y NL
Este artículo trata sobre clases de idiomas para una máquina de Turing determinista. El artículo sobre la utilidad de Unix se llama nl .La clase de lenguaje L es el conjunto de lenguajes que son decidibles en una máquina de Turing determinista usando memoria adicional para una entrada de longitud n.
La clase de lenguajes NL es el conjunto de lenguajes que son decidibles en una máquina de Turing no determinista usando memoria adicional para una entrada de longitud n.
Ejemplos:
- Sea el lenguaje un grafo dirigido en el que hay un camino de s a t , entonces
NL-problemas completos
Un convertidor de memoria de registro es una máquina de Turing con tres cintas: una cinta de entrada de solo lectura, una cinta de salida de solo escritura y una cinta de trabajo que no puede usar más de O(log(n)) celdas.
La función calculada por dicho convertidor se denomina función calculada con memoria logarítmica .
El problema A se reduce logarítmicamente de la memoria al problema B si hay una función logarítmica de la memoria que reduce el problema A al problema B. Denotado
Un idioma se llama NL-completo si pertenece a NL y cualquier idioma en NL se puede reducir logarítmicamente de memoria.
Teorema:
Consecuencia:
Si un idioma completo NL pertenece a L, entonces L = NLDeclaración:
PATH es una tarea completa de NL.Consecuencia:
.
Teorema de Immermann
clase coNL : idiomas cuyos complementos están en NL.
Teorema de Immermann:
NL=coNLLiteratura
- Michael Sipser: "Introducción a la Teoría de la Computación"
| Clases de complejidad de algoritmos | |
|---|---|
| Considerado ligero |
|
| Se supone que es difícil | |
| Considerado difícil |
|