La complejidad del espacio de reconocer palíndromos de Watson-Crick

Question

Tengo el siguiente problema algorítmico:

determinar el espacio de Turing complejidad de reconocer cadenas de ADN que son palíndromos Watson-Crick.

palíndromos

Watson-Crick son cadenas cuyo complemento inverso es la cadena original. La complemento se define carta-sabia, inspirado por ADN:. A es el complemento de T y C es el complemento de G. Un ejemplo simple para un WC-palíndromo se ACGT

Yo he llegado con dos formas de resolver esto.

Uno requiere $ \ mathcal {O} (n) $ espacio.

• lectura de la entrada Una vez que la máquina se realiza. La cinta de entrada se debe copiar en la cinta de trabajo en orden inverso.
• La máquina comienza a leer las cintas de entrada y de trabajo de la izquierda y comparar cada entrada para verificar la celda de la cinta de trabajo es el complemento de la célula en la entrada. Esto requiere $ \ mathcal {O} (n) $ espacio.

El otro requiere $ \ mathcal {O} (\ log n) $ espacio.

• Durante la lectura de la entrada. Contar el número de entradas en la cinta de entrada.
• Cuando la lectura de la cinta de entrada se realiza
  • copiar el complemento de la carta en la cinta de trabajo
  • copiar la letra L hasta el final de la cinta de trabajo
• (Punto de bucle) Si el contador = 0, claro que sí los worktape y escritura, y luego detenga
• Si la cinta de entrada lee L
  • Mover la cabeza de entrada a la izquierda por el número de veces indicado por el contador (requiere un segundo contador)
• Si la cinta de entrada lee R
  • mover el cabezal de entrada a la derecha por el número de veces indicado por el contador (requiere un segundo contador)
• Si la celda que contiene el valor de la worktape coincide con la celda actual en la cinta de entrada
  • disminuir el contador por dos
  • Mover una a la izquierda oa la derecha dependiendo de si R o L es el worktape respectivamente
  • copiar el complemento de L o R para el worktape en lugar de la corriente L o R
  • continuar el bucle
• Si los valores no coinciden, desactive la worktape y escribir no, entonces detenerse

Esto sale a alrededor de $ 2 \ log n + 2 $ de espacio para el almacenamiento de ambos contadores, el complemento actual, y el valor L o R.

Mi problema

El primero requiere tanto tiempo lineal y el espacio. El segundo requiere $ \ frac {n ^ 2} {2} $ y $ tiempo \ log n $ espacio. Me dieron el problema de la cita y se acercó con estos dos enfoques, pero no sé cuál de ellos para ir con. Sólo necesito para dar el espacio complejidad del problema.

La razón por la que estoy confundido

Yo tendería a decir que el segundo es la mejor opción ya que es mejor en términos de tiempo, pero esa respuesta sólo viene de mí tener suerte y dar con un algoritmo. Parece como si yo quiero dar la complejidad del espacio de algo, que no requeriría suerte en dar con el algoritmo correcto. ¿Me estoy perdiendo de algo? Debería ser incluso llegar a una solución al problema para responder a la complejidad espacial?

Answer 1

Aviso Legal El siguiente algoritmo no utiliza el modelo estándar de la complejidad del espacio sublinear (ver WP: DSPACE ), porque se escribe en la cinta de entrada. Además, el conjunto de palíndromos (Watson-Crick) no está en $ \ mathsf {DSPACE} (\ mathcal {O} (1)) = \ mathsf {REG} $. Sin embargo, es una solución en el lugar para muchos propósitos prácticos (por ejemplo, si cada letra es un char en C).

Para demostrar que un problema tiene una complejidad espacio específico, uno necesita, en general para llegar a un algoritmo que tiene esa complejidad espacial. Esto puede requerir prueba y error, pero un mejor enfoque es tener una buena comprensión del problema que usted está mirando, y una buena cantidad de experiencia en algoritmos y complejidad.

En este ejemplo en particular, hay un tercer algoritmo que no necesita ningún espacio adicional y requiere $ O (n ^ 2) $ time complejidad. Este algoritmo sería el espacio constante.

Pista: ¿por qué el uso de espacio adicional, cuando se puede utilizar el espacio ocupado por la entrada

Sugerencia: cremallera de ida y vuelta a través de la cadena de control de un carácter a la vez - utilizar el estado de la máquina de Turing que recordar que el personaje va a registrar y borrar los caracteres ya ha comprobado

.

Answer 2

La forma en que se hizo la pregunta que se debe llegar a un límite superior y límite inferior de la complejidad del espacio.

La primera parte se realiza generalmente mediante la presentación de un algoritmo para su problema, pero una reducción a algún otro problema bien estudiado también funcionaría (e indirectamente producir un algoritmo, también). Dado que usted no se considera una complejidad combinada (tiempo y espacio) sólo las cuestiones de espacio, incluso si aumenta el tiempo. Así que has encontrado un límite superior de $ \ mathcal {O} (\ log n) $.

La segunda parte es por lo general un complicado mucho, pero se puede demostrar fácilmente que el espacio constante no es suficiente, ya que esto haría que su lenguaje regular. Usando el lema de bombeo con, por ejemplo, $ a ^ lb ^ {2l} a ^ l $, donde $ l $ es el número supone el bombeo hará el truco. Esto deja una gran brecha entre $ \ omega (1) $ y $ \ mathcal {O} (\ log n) $.

He encontrado un ejercicio (ver ejercicio 6) que da algunas pistas. Si interpreto su pista correctamente, intente demostrando que hay muchas diferentes clases de equivalencia de la relación Myhill-Nerode para cada tamaño de entrada. Esto es similar al argumento de que no se puede distinguir más de $ c \ cdot \ gamma ^ {s (n)} $ cadenas de longitud $ n $ (donde $ \ Gamma $ es el alfabeto de cinta y $ s (n) $ su complejidad espacio). Esto le dará un límite inferior de $ \ Omega (\ log n) $.

---

Tenga en cuenta que no es necesario preocuparse por el complemento de las cartas ya que esta operación es trivial, por lo que todo lo que funciona para palíndromos ordinarios pueden ser modificados con unos pocos más estados para resolver su problema.

Answer 3

Es muy probable que el tiempo-espacio compensación para los palíndromos sostiene también en su caso. Este resultado establece que una máquina de Turing reconocer palíndromos en el espacio $ S $ debe tomar tiempo $ \ Omega (n ^ 2 / S) $, es decir, $$ \ textrm {Tiempo} \ tiempos \ textrm {espacio} = \ Omega (n ^ 2). $$ En su caso, el primer algoritmo tiene $ TS = \ Theta (n ^ 2) $, y el segundo tiene $ TS = \ Theta (n ^ 2 \ log n) $. También se puede demostrar que el límite inferior para el espacio es $ \ Omega (\ log n) $. No he podido encontrado cuál es la mejor cota superior - es decir, si hay un algoritmo utilizando el espacio logarítmico y $ O (n ^ 2 / \ log n) $, o, en general, por lo que los valores de $ S $ que puede lograr un tiempo $ \ Omega (n ^ 2 / S) $. A modo de ejercicio, puede intentar encontrar otros algoritmos de interpolación, híbridos sus dos algoritmos.