ÁREA DE TEORIA DA COMPUTAÇÃO
Subárea: Complexidade Algébrica
Complexidade e Computação sobre os Reais
A teoria clássica da computação tem suas origens no
trabalho de Gödel,
Turing, Church, e Kleene e tem sido um ferramental extraordinariamente
bem sucedido para a teoria da computação. Foi em 1989,
que S. Smale,
M. Shub e L. Blum introduziram uma teoria da computação e
complexidade sobre
um anel ou corpo arbitrário R, que mais tarde seria
publicada no livro
Complexity and Real Computation (L. Blum, F. Cucker, M. Shub and
S. Smale,
Springer Verlag, 1998), no qual os autores advogam que a teoria
clássica da computação
estabelece fundamentos inapropriados à computação
científica moderna em
que a maioria dos algoritmos são algoritmos sobre números reais.
O objetivo do livro é então desenvolver uma teoria formal da
computação que
integre os principais temas da teoria clássica e que seja mais
diretamente aplicável a problemas em matemática, análise
numérica, e computação científica.
No desenrolar do trabalho, os autores levam em consideração
problemas fundamentais como: O conjunto de Mandelbrot é decidível?
Para mapeamentos quadráticos simples, o conjunto de Julia é
um conjunto que pára? Qual é a complexidade real do
método de Newton? Existe um algoritmo para decidir o problema da
mochila em um número polinomial de passos?
O Nullstellensatz de Hilbert é intratável?
O problema de localizar um zero real de um polinômio de grau quatro
é intratável? A programação linear é
tratável sobre os reais?
Classes de Complexidade definidas em termos de Eliminação de Quantificadores
Talvez a principal contribuição do artigo original de
Blum, Shub e Smale (1989)
tenha sido a definição da classe NP sobre os reais,
e, em geral sobre um anel
ou corpo arbitrário R. Tal qual na complexidade
computacional clássica, o problema "P=?NP" é o principal
problema em aberto no modelo de Blum-Shub-Smale
e em suas variantes. Pode-se, no entanto, fazer a mesma pergunta sobre os
complexos, e até mesmo sobre estruturas arbitrárias, como
faz Bruno Poizat em Les Petits Cailloux (1995). A idéia
principal de Poizat é retomar o problema em toda sua generalidade
sob a perspectiva da teoria dos modelos,
e definir classes de complexidade em termos de eliminação de
quantificadores.
Segundo Koiran (1999), além de sua generalidade, é de se
salientar os seguintes pontos na abordagem de Poizat:
(i) a proposta de um modelo de cálculo baseado em circuitos que poderia
substituir as máquinas de Blum-Shub-Smale;
(ii) o estabelecimento de uma correlação entre o problema
"P=?NP" e a propriedade de eliminação de quantificadores: para toda
estrutura M, "P=NP em M"
se e somente se é possível eliminar um bloco de
quantificadores existenciais em tempo polinomial (representando a
fórmula eliminante por um circuito no sentido de M).
Complexidade Algébrica
Em Completeness and Reduction in Algebraic Complexity Theory
P. Bürgisser lembra que uma das teorias mais importantes e bem sucedidas
em complexidade computacional é a da NP-completude.
Trata-se de uma teoria discreta baseada no modelo da máquina de
Turing, e que permite uma classificação de problemas
computacionais discretos conforme sua dificuldade algorítmica.
Enquanto que as máquinas de Turing formalizam algoritmos que
operam sobre cadeias finitas de símbolos sobre um alfabeto finito,
nos modelos algébricos de computação o
passo computacional básico é uma operação
aritmética (ou comparação) de
elementos de um corpo fixo, por exemplo os reais. A partir de então,
assume-se aritmética exata. O modelo de Blum-Shub-Smale combinou os
modelos algébricos de computação existentes com o
conceito de uniformidade e desenvolveu uma teoria de NP-completude sobre os
reais. Porém, dez anos antes da publicação do artigo
original de Blum-Shub-Smale, Valiant (1979, 1982) havia proposto um
análogo da teoria da NP-completude em um contexto inteiramente
algébrico, relacionado ao seu famoso resultado
sobre o permanente. Enquanto que a parte de sua teoria baseada na
abordagem de Turing (#P-completude) é hoje padrão e bem
conhecida na comunidade de teoria da computação, seu
resultado de completude algébrica para os permanentes recebeu muito
menos atenção. No seu livro, P. Bürgisser estende a
abordagem de Valiant, e torna mais claras suas
conexões com o modelo clássico (discreto) e o modelo de
Blum-Shub-Smale.
(A primeira exposição da teoria algébrica de Valiant com
demonstrações detalhadas foi o artigo de J. von zur Gathen
(1987).)
Bibliografia
L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over
the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21:1-46, 1989.
L. Blum, F. Cucker, M. Shub & S. Smale. Complexity and Real Computation.
Springer, 1998. ISBN: 0-387-98281-7
P. Buügisser. Completeness and Reduction in Algebraic Complexity Theory.
Algorithms and Computation in Mathematics, No. 7, Springer Verlag 2000,
168 + xii pp. ISBN 3-540-66752-0
P. Bürgisser, M. Clausen, and M.A. Shokrollahi. Algebraic Complexity Theory.
Grundlehren der mathematischen Wissenschaften, No. 315,
Springer Verlag 1997, 618 + xxiii pp. ISBN 3-540-60582-7
J. von zur Gathen. Feasible arithmetic computations: Valiant's hypothesis.
J. Symb. Comp. 4:137-172, 1987.
P. Koiran. Complexité et décidabilité pour les modèles de calcul
algébriques et analogiques. Mémoire d'habilitation.
Université Claude Bernard Lyon 1. 10 Décembre 1999.
(http://www.ens-lyon.fr/~koiran/Publis/memoire.ps.Z)
B. Poizat. Les petits cailloux. Une approche modèle-théorique de l'Algorithmie, Nur al-Mantiq wal-Ma'rifah; Aléas Editeur,
15 quai Lassagne, 69001 Lyon, France.
L.G. Valiant. Completeness classes in algebra. In Proc. 11th ACM STOC,
pages 249-261, 1979.
L.G. Valiant. The complexity of computing the permanent. Theoret. Comp. Sc.
8:189-201, 1979.
L.G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic
(An international Symposium held in honor of Ernst Specker),
pages 365-380. Monographie No.30 de l'Enseignement Mathematique, 1982.
Última atualização: 16 de Setembro de 2002, 11:24:06 GMT-0200.
