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 ) .
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 ) ) .
Respuestas:
Escribes en los comentarios :
¿Puedes usar un argumento similar para mejorar los límites?
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.
fuente