Probar que una función booleana computable en T (n) por una máquina RAM está en DTIME (T (n) ^ 2)

10

La pregunta es el ejercicio 1.9 del libro de Arora-Barak Complejidad computacional: un enfoque moderno :


Defina una máquina RAM Turing para que sea una máquina Turing que tenga memoria de acceso aleatorio. Formalizamos esto de la siguiente manera: la máquina tiene una matriz infinita A que se inicializa en todos los espacios en blanco. Accede a esta matriz de la siguiente manera. Una de las cintas de trabajo de la máquina se designa como la cinta de dirección. Además, la máquina tiene dos símbolos especiales del alfabeto denotados por R y W y un estado adicional que denotamos por q_access. Cada vez que la máquina ingresa q_access, si su cinta de direcciones contiene 'i'R (donde' i 'denota la representación binaria de i), el valor A [i] se escribe en la celda junto al símbolo R. Si su cinta contiene 'i'Wa (donde a es un símbolo en el alfabeto de la máquina), entonces A [i] se establece en el valor a.

Demuestre que si una función booleana es computable dentro del tiempo T ( n ) (durante algún tiempo T constructible ) por una RAM TM, entonces está en D T I M E ( T ( n ) 2 ) .FT(norte)TreTyoMETROmi(T(norte)2)


La solución trivial mediante el uso de pares de grabación de cinta adicionales (dirección, valor) resulta estar en , ya que esa cinta puede ser de tamaño O ( T ( n ) 2 ) con O ( T ( n ) ) pares, mientras que la dirección de cada par puede ser de tamaño O ( T ( n ) ) .reTyoMETROmi(T(norte)3)O(T(norte)2)O(T(norte))O(T(norte))

cc
fuente
¿Cómo sabes el límite en el tamaño de la dirección? ¿No podría ser mi primera escritura ? Y si puede vincularlo a T ( n ) , el tamaño de la dirección es log ( T ( n ) ) , no T ( n ) . 22T(norte)T(norte)Iniciar sesión(T(norte))T(norte)
Xodarap
1
Como la dirección debe escribirse en la cinta mediante una máquina Turing de tiempo , el tamaño (es decir, la longitud de la cadena) de la dirección no puede exceder O ( T ( n ) ) , el espacio de dirección accesible es O ( 2 T ( n ) ) . T(norte)O(T(norte))O(2T(norte))
cc
3
Tenga en cuenta que Arora y Barak solicitan explícitamente en su introducción otras respuestas no publicadas a sus preguntas. Vea también la política sobre preguntas de tarea .
Kaveh
Lo siento por eso. Yo solo estudio el libro y me preocupa esa pregunta. No sé si tal simulación realmente existe o si es solo un error tipográfico. Si conoce la respuesta, envíeme un correo electrónico en privado a [email protected], y luego cerraré la pregunta. O(T(norte)2)
cc
Puede encontrar más en el primer capítulo del manual de informática teórica.
Kaveh

Respuestas:

2

Escribes en los comentarios :

T(norte)O(T(norte))

¿Puedes usar un argumento similar para mejorar los límites?

O(T(norte)2)O(T(norte))O(T(norte))

que mencionas en la pregunta? Es posible que deba recordar qué operaciones son posibles en tiempo constante en la RAM, es decir, utilizando la definición precisa que utilizan los autores.

Rafael
fuente
Espero que esta pista sea lo suficientemente vaga como para respetar los deseos de los autores del libro, pero también sea de alguna ayuda. (Heurística: le diría a un estudiante tanto si el problema se dio como ejercicio. Probablemente no en un examen).
Raphael