Dissertação

Complexity with Costing and Stochastic Oracles EVALUATED

Pretende-se estudar nesta dissertação o poder computacional que se obtêm combinando um dispositivo digital, como a máquina de Turing, com um dispositivo analógico, como uma experiência física que serve de oráculo para a máquina. Definem-se os principais componentes destes sistemas híbridos, a que chamamos máquinas de Turing analógicas-digitais, e analiza-se o seu poder computational sujeito a recursos polinomiais. Investigam-se três tipos de oráculos motivados por experiências físicas, nomeadamente oráculos bilaterais, oráculos de limiar e oráculos de desvanecimento. O oráculo fornece informação qualitativa que auxilia a computação da máquina de Turing. Também se consideram variantes no protocolo entre a máquina de Turing e o oráculo, de modo que as questões ao oráculo sejam traduzidas para números reais com precisão infinita, precisão ilimitada ou precisão finita. Para cada caso são provadas minoraçõs e majorações nas classes de complexidade computadas por estes sistemas.
complexidade computacional, oráculo físico, sistema híbrido, teoria da medição, complexidade não-uniforme

Junho 27, 2013, 14: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