Hispanopedia Wiki
Articulo de referencia

L (complejidad)

Las relaciones entre varias clases de complejidad relacionadas con L. Producidas al rastrear las diversas declaraciones de contención de clases de Complexity Zoo . En la teoría ...

Hispanopedia WikiContenido en espanolLectura gratuita
Las relaciones entre varias clases de complejidad relacionadas con L. Producidas al rastrear las diversas declaraciones de contención de clases de Complexity Zoo .

En la teoría de la complejidad computacional , L (también conocido como LSPACE , LOGSPACE o DLOGSPACE ) es la clase de complejidad que contiene problemas de decisión que pueden ser resueltos por una máquina de Turing determinista utilizando una cantidad logarítmica de espacio de memoria escribible . [ 1 ] [ 2 ] Formalmente, la máquina de Turing tiene dos cintas , una de las cuales codifica la entrada y solo puede ser leída, [ 3 ] mientras que la otra cinta tiene un tamaño logarítmico pero puede escribirse además de leerse. El espacio logarítmico es suficiente para mantener un número constante de punteros a la entrada [ 1 ] y un número logarítmico de indicadores booleanos, y muchos algoritmos básicos de espacio logarítmico utilizan la memoria de esta manera.

Problemas completos y caracterización lógica

Todo problema no trivial en L es completo bajo reducciones de espacio logarítmico , [ 4 ] por lo que se requieren reducciones más débiles para identificar nociones significativas de L- completitud, siendo las más comunes las reducciones de primer orden .

Un resultado de 2004 de Omer Reingold muestra que USTCON , el problema de si existe un camino entre dos vértices en un grafo no dirigido dado , está en L , lo que muestra que L = SL , ya que USTCON es SL -completo. [ 5 ]

Una consecuencia de esto es una caracterización lógica simple de L : contiene precisamente aquellos lenguajes expresables en lógica de primer orden con un operador de cierre transitivo conmutativo añadido (en términos de teoría de grafos , esto convierte cada componente conexa en una camarilla ). Este resultado tiene aplicación a los lenguajes de consulta de bases de datos : la complejidad de datos de una consulta se define como la complejidad de responder a una consulta fija considerando el tamaño de los datos como la entrada variable. Para esta medida, las consultas a bases de datos relacionales con información completa (sin noción de nulos ), como se expresa por ejemplo en álgebra relacional, están en L.

L es una subclase de NL , que es la clase de lenguajes decidibles en espacio logarítmico en una máquina de Turing no determinista . Un problema en NL puede transformarse en un problema de alcanzabilidad en un grafo dirigido que representa estados y transiciones de estado de la máquina no determinista, y el límite del espacio logarítmico implica que este grafo tiene un número polinomial de vértices y aristas, de lo cual se sigue que NL está contenido en la clase de complejidad P de problemas resolubles en tiempo polinomial determinista. [ 6 ] Por lo tanto , L  ⊆ NL ⊆ P . La inclusión de L en P también puede probarse más directamente: un decisor que usa espacio O (log n ) no puede usar más de 2 O (log n ) = n O (1) tiempo, porque este es el número total de configuraciones posibles.       

L se relaciona además con la clase NC de la siguiente manera: NC 1  ⊆ L ⊆ NL ⊆ NC 2 . En otras palabras, dado un ordenador paralelo C con un número polinomial O ( n k ) de procesadores para alguna constante k , cualquier problema que pueda resolverse en C en tiempo O (log n ) está en L , y cualquier problema en L puede resolverse en tiempo O (log 2 n ) en C .       

Problema sin resolver en informática
⁠L=¿PAG{\displaystyle {\mathsf {L}}{\overset {?}{=}}{\mathsf {P}}}⁠
Más problemas sin resolver en informática

Entre los problemas abiertos importantes se incluyen si L  = P , [ 2 ] y si L = NL . [ 7 ] Ni siquiera se sabe si L = NP . [ 8 ]     

La clase relacionada de problemas de funciones es FL . FL se usa a menudo para definir reducciones de espacio logarítmico .

Versiones aleatorias

Así como P tiene varias versiones aleatorias: BPP , ZPP , PP y RP , también hay varias versiones aleatorias de L.

La probabilidad de error acotada L ( BPL ) se define como BPP , como la clase de complejidad de problemas resolubles con una máquina de Turing de espacio logarítmico tal que:

  • Además de las cintas habituales de una máquina de Turing de espacio logarítmico, la máquina también utiliza una cinta llena de bits aleatorios.
  • La aleatoriedad es de solo lectura y unidireccional. Es decir, el cabezal de lectura de la cinta aleatoria solo puede moverse en una dirección. Para consultar un bit aleatorio anterior, la máquina debe almacenarlo en la cinta de trabajo.
  • La máquina de Turing tiene que detenerse para cada entrada y cada cinta aleatoria.
  • Si la respuesta es "sí", la máquina acepta con una probabilidad de al menos 2/3. Si la respuesta es "no", la máquina rechaza con una probabilidad de al menos 2/3.

Está contenido en NC 2 , que está contenido en P . [ 9 ]

BP•L se define igual que BPL , excepto que la máquina puede leer la cinta aleatoria tanto hacia adelante como hacia atrás. Contiene BPL . También es exactamente igual a la clase de lenguajes que son casi espacio logarítmico: un lenguaje es casi espacio logarítmico si, en relación con casi todos los oráculos, el lenguaje está en L. [ 10 ]

ZP•L se define como BP•L , excepto que la máquina puede generar "desconocido" y nunca debe cometer un error (es decir, aceptar cuando la respuesta es "no" y viceversa). La relación de ZP•L con BP•L es la misma que la de ZPP con BPP . Contiene a BPL y está contenido en BP•L . [ 10 ]

La L aleatoria ( RL ) se define como BPL :

  • Además de las cintas habituales de una máquina de Turing de espacio logarítmico, la máquina también utiliza una cinta unidireccional de solo lectura llena de bits aleatorios.
  • La máquina de Turing tiene que detenerse para cada entrada y cada cinta aleatoria.
  • Si la respuesta es "sí", acéptela con una probabilidad de al menos 1/2.
  • Si la respuesta es "no", recházalo siempre.

Además, siempre debe ejecutarse en tiempo polinomial (ya que de lo contrario solo obtendríamos NL ) . Se sospecha firmemente que RL = L. [ 11 ]

Tanto BPL como RL están contenidos en la clase de Steve . [ 12 ]

La L probabilística ( PL ) tiene la misma relación con L que PP con P :

  • Si la respuesta es "sí", acéptela con una probabilidad de al menos 1/2.
  • Si la respuesta es 'no', rechácela con una probabilidad de al menos 1/2.

Contiene BPL y está contenido por NC 2. [ 13 ]

Propiedades adicionales

L es bajo en sí mismo, porque puede simular consultas de oráculo en espacio de registro (en términos generales, "llamadas a funciones que utilizan espacio de registro") en espacio de registro, reutilizando el mismo espacio para cada consulta.

Otros usos

La idea principal del espacio logarítmico es que se puede almacenar un número de magnitud polinómica en dicho espacio y utilizarlo para recordar punteros a una posición de la entrada.

Por lo tanto, la clase logspace resulta útil para modelar cálculos donde la entrada es demasiado grande para caber en la RAM de un ordenador. Las secuencias largas de ADN y las bases de datos son buenos ejemplos de problemas en los que solo una parte constante de la entrada estará en la RAM en un momento dado y donde disponemos de punteros para calcular la siguiente parte de la entrada que se va a analizar, utilizando así únicamente memoria logarítmica.

Véase también

Notas

  1. 1 2 Sipser (1997) , pág. 295, Definición 8.12 
  2. ^ Garey y Johnson (1979) , pág. 177 
  3. ↑ En una cinta de entrada de lectura/escritura, se podría obtener una cantidad lineal de memoria mediante el empaquetamiento de símbolos (como en la demostración del teorema de aceleración lineal ), evitando así la restricción del espacio logarítmico.
  4. ↑ Véase Garey y Johnson (1979) , pág. 179, Teorema 7.13 (afirmación 2) 
  5. ↑ Reingold, Omer (2005). Conectividad ST no dirigida en el espacio logarítmico . STOC'05: Actas del 37.º Simposio Anual de la ACM sobre Teoría de la Computación . ACM, Nueva York. págs. 376–385 . doi : 10.1145/1060590.1060647 . MR 2181639. ECCC TR04-094 .   
  6. ↑ Sipser (1997) , Corolario 8.21, pág. 299.
  7. ↑ Sipser (1997) , pág. 297 ; Garey y Johnson (1979) , pág. 180  
  8. ↑ "Teoría de la complejidad: ¿es posible que L = NP?" .  
  9. ↑ Borodin, A.; Cook, S.; Pippenger, N. (1983-07-01). "Computación paralela para anillos bien dotados y máquinas probabilísticas con recursos limitados espacialmente" . Information and Control . 58 (1): 113– 136. doi : 10.1016/S0019-9958(83)80060-6 . ISSN 0019-9958 . 
  10. 1 2 Nisan, Noam (1993-01-04). "Sobre la lectura única frente al acceso múltiple a la aleatoriedad en el espacio logarítmico" . Theoretical Computer Science . 107 (1): 135– 144. doi : 10.1016/0304-3975(93)90258-U . ISSN 0304-3975 . 
  11. ↑ Reingold, Omer; Trevisan, Luca; Vadhan, Salil (21 de mayo de 2006). «Paseos pseudoaleatorios en digrafos regulares y el problema RL vs. L» . Actas del trigésimo octavo simposio anual de la ACM sobre Teoría de la Computación . STOC '06. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 457–466 . doi : 10.1145/1132516.1132583 . ISBN  978-1-59593-134-4.
  12. ↑ Nisan, Noam (1994-03-01). "RL ⊆ SC" . Complejidad Computacional . 4 (1): 1– 11. doi : 10.1007/BF01205052 . ISSN 1420-8954 . 
  13. ↑ Cook, Stephen A. (1985-01-01). "Una taxonomía de problemas con algoritmos paralelos rápidos" . Information and Control . Conferencia Internacional sobre Fundamentos de la Teoría de la Computación. 64 (1): 2– 22. doi : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 . 

Referencias

  • Arora, Sanjeev; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4. Zbl 1193.68112 . 
  • Papadimitriou, Christos (1993). Complejidad computacional (1.ª  ed.). Addison Wesley. Capítulo 16: Espacio logarítmico, pp.  395–408. ISBN 0-201-53082-1.
  • Sipser, Michael (1997). Introducción a la teoría de la computación . PWS Publishing. Sección 8.4: Las clases L y NL, págs.  294–296. ISBN 0-534-94728-X.
  • Garey, MR ; Johnson, DS (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. Sección 7.5: Espacio logarítmico, págs.  177–181 . ISBN 0-7167-1045-5. MR 0519066 . OCLC 247570676 .  
  • Cook, Stephen A .; McKenzie, Pierre (1987). "Problemas completos para el espacio logarítmico determinista" (PDF) . Journal of Algorithms . 8 (3): 385–394 . doi : 10.1016/0196-6774(87)90018-6 . ISSN 0196-6774 .