SL (complejidad)

SL (complejidad)

SL (complejidad)

En teoría de la complejidad computacional, la clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, tal que:

  1. Si la respuesta es positiva, existe uno o más cómputos de la máquina que aceptan.
  2. Si la respuesta es negativa, todos los cómputos de la máquina rechazan la entrada.
  3. Si la máquina puede hacer una transición no determinista entre una configuración A y una configuración B, también puede hacer una transición de B hacia A (condición de simetría).

En 2004 se demostró que esta clase de complejidad es equivalente a L. En otras palabras, la condición de simetría en la máquina de Turing no determinista la hace equivalente a una máquina de Turing determinista.

Referencias

  • H. R. Lewis y C. H. Papadimitriou. Symmetric space-bounded computation, Theoretical Computer Science 19:161-187, 1982.
  • O. Reingold. Undirected st-connectivity in log-space, no publicado, 2004
Obtenido de "SL (complejidad)"

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Complejidad computacional — Saltar a navegación, búsqueda La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos… …   Wikipedia Español

  • Complejidad (álbum) — Complejidad Álbum de Efecto Mariposa Publicación 24 de mayo de 2005 Grabación Madrid …   Wikipedia Español

  • Complejidad social — Saltar a navegación, búsqueda Complejidad social El segundo camino que ha tomado la naturaleza para formar sociedades complejas es el de desarrollar una especie con suficiente inteligencia como para pasar sus conocimientos a las generaciones… …   Wikipedia Español

  • complejidad — ‘Cualidad de complejo’: «No negaba la complejidad del problema» (Belli Mujer [Nic. 1992]). Es preferible a complexidad, voz poco usada, pero que parece estar recuperando cierta vigencia, especialmente en algunas zonas de América, por influencia… …   Diccionario panhispánico de dudas

  • complejidad — sustantivo femenino 1. (no contable) Característica de complejo: Dada la complejidad del problema, habrá que examinarlo detenidamente …   Diccionario Salamanca de la Lengua Española

  • complejidad — o complexidad sustantivo femenino complicación. * * * Sinónimos: ■ dificultad, complicación, confusión, laberinto, embrollo, lío, diversidad …   Diccionario de sinónimos y antónimos

  • complejidad — f. Cualidad de complejo …   Diccionario de la lengua española

  • Complejidad biológica — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Complejidad ciclomática — La Complejidad Ciclomática (en inglés, Cyclomatic Complexity) es una métrica del software que proporciona una medición cuantitativa de la complejidad lógica de un programa. Es una de las métricas de software de mayor aceptación, ya que ha sido… …   Wikipedia Español

  • Complejidad irreducible — Existen desacuerdos sobre la neutralidad en el punto de vista de la versión actual de este artículo o sección. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Complejidad en los juegos — Este artículo o sección sobre ocio necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 11 de junio de 2008. También puedes ayudar… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”