Dissertação

BPP//log (Random Walks as Oracles) EVALUATED

O emparelhamento de máquinas de Turing com oráculos é uma das técnicas utilizadas para aumentar o poder computacional das máquinas ou para melhorar a sua eficiência. Nesta dissertação é estudado o poder computacional de máquinas de Turing analógico-digitais, ou seja, máquinas de Turing acopladas com experiências físicas, que são tratadas como oráculos. Consideramos um oráculo físico genérico e abstracto, obedecendo a certos axiomas, analisamos o seu poder computacional e utilizamo-lo para abstrair algum do trabalho já feito relativamente a máquinas de Turing analógico-digitais. Mostramos também que estes oráculos permitem generalizar a máquina de Turing probabilística, comparando a máquina analógico-digital obtida com a máquina probabilística que tem números reais como probabilidade de transição. Depois, concretizamos o nosso oráculo genérico com a experiência do passeio aleatório, apresentando um interessante estudo sobre a experiência. De seguida, limitamos o número de chamadas ao oráculo, com o objectivo de estudar a estrutura interna de BPP//log*. Analisamos o poder computacional das máquinas de passeio aleatório com certos limites no número de chamadas ao oráculo. Provamos um importante resultado sobre classes de complexidade não-uniforme para o caso probabilístico. Por fim, apresentamos uma hierarquia de classes em BPP//log*, correspondente às máquinas de Turing analógico-digitais com o número de chamadas ao oráculo limitado por certas funções do tamanho do input.
Máquinas de Turing, Oráculos físicos, Complexidade não-uniforme, Passeios aleatórios, BPP//log*

Maio 8, 2015, 15:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

José Félix Gomes da Costa

Departamento de Matemática (DM)

Professor Associado