|
Abstract:
|
Este trabalho aponta que as definições existentes de funções computadas por máquinas de Turing não determinísticas não permitem adaptar diretamente todos os problemas de decisão para funções e não justificam a obtenção, quando é, em tempo polinomial de suas saídas. Por esse motivo, propõe uma variação, baseada na associação de uma árvore de computação à estratégia de divisão e conquista, denominada máquina de Turing não determinística com combinadora, capaz dessa adaptação e com uma definição de tempo bem justificada. Além disso, exemplifica a variação proposta com máquinas que computam as funções das classes #P e OptP, as funções características dos complementos das linguagens decididas por máquinas de Turing não determinísticas e uma função que resolve o Problema de Deutsch-Jozsa. |
