ALGORITMOS ALGEBRICOS, O SMART BRAIN E O PROBLEMA P VERSUS NP

Trata-se de um livro que une a Teoria da Computação com a Lógica Simbólica. Inicia-se o corpo do texto expondo um novo modelo computacional, composto pelo que o autor chama de algoritmos algébricos. Um algoritmo algébrico computa números reais, ao invés de cadeias. Isso possibilita que importemos para a Teoria da Computação todo o conhecimento adquirido em Álgebra, Cálculo Integral e Diferencial e Matemática Discreta. A vantagem deste modelo sobre os já conhecidos consiste no fato de que a saída de um algoritmo algébrico legítimo pode ser calculada por uma fórmula, que o autor apresenta e demonstra, definida em função da entrada e da descrição da máquina. Além disso, uma máquina de Turing pode ser convertida a um algoritmo algébrico legítimo e vice-versa, como é mostrado no livro. Com isso, mostra-se que, dado um algoritmo qualquer, podemos calcular a sua saída por meio de uma expressão matemática, sem a necessidade de se computar a máquina, com ganhos notáveis em termos de tempo de execução no contexto da análise de complexidade de tempo no pior caso. Esta teoria traz consigo repercussões profundas em Teoria da Complexidade.