Prove que uma função booleana computável em T (n) por uma máquina RAM está em DTIME (T (n) ^ 2)

10

A questão é o exercício 1.9 do livro de Arora-Barak, Computational Complexity - A Modern Approach :

Defina uma máquina de RAM Turing para ser uma máquina de Turing com memória de acesso aleatório. Formalizamos da seguinte maneira: A máquina possui uma matriz infinita A que é inicializada em todos os espaços em branco. Ele acessa esse array da seguinte maneira. Uma das fitas de trabalho da máquina é designada como a fita de endereço. Além disso, a máquina possui dois símbolos especiais do alfabeto denotados por R e W e um estado adicional que denotamos por q_access. Sempre que a máquina digitar q_access, se sua fita de endereço contiver 'i'R (onde' i 'denota a representação binária de i), o valor A [i] será gravado na célula ao lado do símbolo R. Se a fita contiver 'i'Wa (onde a é algum símbolo no alfabeto da máquina), então A [i] é definido como o valor a.

Mostre que se uma função booleana é computável no tempo (por algum tempo construtível ) por uma RAM TM, então ela está em .fT(n)TDTIME(T(n)2)

A solução trivial, usando pares adicionais de gravação em fita (endereço, valor), está em , pois essa fita pode ser do tamanho com pares enquanto o endereço de cada par pode ser do tamanho O ( T ( n ) ) .DTIME(T(n)3)O(T(n)2)O(T(n))O(T(n))

complexity-theory turing-machines machine-models simulation cc
fonte
Como você sabe o limite do tamanho do endereço? Minha primeira gravação não pôde ser em ? E se você pode vinculá-lo a , o tamanho do endereço é , não . 22T(n)T(n)log⁡(T(n))T(n)
Xodarap 10/07
11
Como o endereço deve ser gravado na fita por uma máquina de Turing de tempo , o tamanho (ou seja, o comprimento da string) do endereço não pode exceder , o espaço de endereço acessível é . T(n)O(T(n))O(2T(n))
cc
3
Observe que Arora e Barak pedem explicitamente em sua introdução outras respostas para não postar suas perguntas. Veja também a política sobre perguntas de lição de casa .
Kaveh
Desculpe por isso. Eu apenas estudo o livro sozinho e fico preocupado com essa pergunta. Não sei se essa simulação realmente existe ou é apenas um erro de digitação. Se você souber a resposta, envie-me um e-mail em particular para [email protected] e depois encerrarei a pergunta. O(T(n)2)
cc
Você pode encontrar mais no primeiro capítulo do manual de ciência da computação teórica.
Kaveh

Respostas:

2

Você escreve nos comentários :

Como o endereço deve ser gravado na fita por uma máquina de Turing de tempo , o tamanho (ou seja, o comprimento da string) do endereço não pode exceder O ( T ( n ) ) .T(n)O(T(n))

Você pode usar um argumento semelhante para melhorar os limites

[A] fita pode ser do tamanho com pares O ( T ( n ) ) enquanto o endereço de cada par pode ser do tamanho O ( T ( n ) ) .O(T(n)2)O(T(n))O(T(n))

você menciona na pergunta? Talvez você precise se lembrar de quais operações são possíveis em tempo constante na RAM, ou seja, usando a definição precisa usada pelos autores.

Rafael
fonte
Espero que essa dica seja vaga o suficiente para respeitar os desejos dos autores do livro, mas também um pouco útil. (Heurística: eu diria a um aluno o mesmo se o problema fosse dado como exercício. Porém, provavelmente não em um exame.)
Raphael