ÁREA DE TEORIA DA COMPUTAÇÃO
Subárea: Teoria dos Modelos
De que se trata?
Teoria dos Modelos estuda a relação entre estruturas (matemáticas) e
linguagens (formais). Um dos seus principais objetivos é determinar os
limites de definibilidade de certas linguagens formais. Dentre as questões
que a Teoria dos Modelos procura responder estão sobretudo:
1. que propriedades podem ou não podem ser expressas em uma certa linguagem?
2. que estruturas ou relações podem ou não podem ser definidas em uma certa linguagem?
Modelos Finitos e Complexidade Descritiva
O uso das técnicas da Teoria dos Modelos "Finitos" para estudar as
classes de complexidade de algoritmos deu origem ao que se chama de
Complexidade Descritiva. Enquanto que na Teoria da Complexidade
Computacional estuda-se a complexidade de problemas em função de um
modelo de máquina de computação baseado em "strings", e mede-se
a complexidade de uma linguagem através dos recursos necessários
(tempo, espaço, etc.) para decidir a pertinência de um determinado
string a uma classe de strings, em Complexidade Descritiva
procura-se estudar a complexidade da descrição, usando uma linguagem
lógica, de uma determinada coleção de estruturas quaisquer.
Tal linha de pesquisa tem demonstrado bastante vigor e aceitação,
e tem contribuido para resolver problemas em teoria da complexidade
que há muito tempo estavam em aberto, tais como:
(1) For all s(n) greater than or equal to log n, nondeterministic space
s(n) is closed under complementation. (Ver página do autor do resultado: Neil Immerman)
(2) A questão "existe uma linguagem de consulta que possa expressar
exatamente as polynomial time generic queries em um banco de dados
relacional?" proposta por A. Chandra & David Harel (1982), foi parcialmente
respondida em 1995, com repercussões em teoria da complexidade, por
Serge Abiteboul e Victor Vianu
(General Chairman do simpósio Principles
of Database Systems - PODS'99): "Inflationary Fixpoint Logic" and
"Partial Fixpoint Logic" have the same expressive power if, and only
if, the complexity classes PTIME and PSPACE co-incide.
Uma vez estabelecido que a lógica de primeira ordem não é
apropriada para formalizar classes de estruturas finitas, a procura por
lógicas
que pudessem descrever exatamente a classe de estruturas finitas
em classes de complexidade específicas (LOGSPACE, NLOGSPACE,
PSPACE, PTIME, etc.) foi desempenhada vigorosamente no início dos anos
80 por N. Immerman (1986) and M. Vardi (1982) que demonstraram,
por exemplo, que existem extensões `naturais' da lógica
de primeira ordem (i.e. as chamadas `lógicas de ponto fixo', que
resultam da adição à lógica de primeira ordem de um operador
para indução monotônica relacional) que caracterizam PTIME sobre
estruturas ordenadas.
A questão fundamental sobre a possibilidade de se encontrar `casamentos'
semelhantes (lógicas versus classes de complexidade) no caso mais geral de
estruturas não necessariamente ordenadas continua em aberto. A ferramenta
chamada `jogos semânticos', desenvolvida para estabelecer o poder
expressivo da lógica de primeira ordem, tem sido bastante útil na
resolução da questão para algumas classes particulares de estruturas.
Os resultados têm se mostrado relevantes em aplicações na área
de linguagens de consulta a bancos de dados relacionais.
Parece haver um pressentimento entre pesquisadores em teoria de modelos
finitos que as técnicas usadas correntemente se tornaram muito
limitadas, e talvez seja tempo de se buscar alguns dos
recentes recursos em teoria de modelos, em particular, estabilidade e/ou
simplicidade, ferramentas suficientemente fortes para permitir uma abertura
de novas perspectivas.
Transcrevemos de Dawar et al. (1998) ("Ordering finite variable
types with generalized quantifiers". In Proc. 13th annual IEEE
symposium on logic in computer science - LICS'98):
"Mostramos que na presença de um conjunto finito de quantificadores
Q, uma ordem <k,Q é definível em
PFP(Q) e em \Sigma1,\omega2(Q)\cap\Pi1,\omega2(Q). Por
outro lado também mostramos que existe um quantificador de
tempo polinomial Q tal que <k,Q é demonstravelmente não
definível em IFP(Q). Não temos ainda qualquer caracterização
destes conjuntos Q sob o qual uma ordem <^k,Q é
definível em IFP(Q).
Para algums quantificadores específicos, provamos alguns resultados
relacionando separação de lógicas de ponto fixo à
separação de classes de complexidade. Estes são
análogos ao teorema de Abiteboul-Vianu. As técnicas usadas
parecem ter algumas limitações e não está claro como
superar isto."
Teoria da Estabilidade
Atualmente uma das subáreas mais ativas da Teoria dos Modelos,
a Teoria da Estabilidade concerne a classificação de estruturas
matemáticas através dos objetos combinatórios que podem
ser nelas definidos.
Nascida no início dos anos 1960s com o Teorema da Categoricidade de
M. Morley, e desenvolvida no programa de pesquisa originalmente concebido por
Saharon Shelah (i.e. "a contagem do número de modelos
não-isomorfos de uma determinada teoria de primeira ordem"),
até o início dos anos 1980s o foco de
atenção da Teoria da Estabilidade estava no trabalho
de Shelah que consistia basicamente da busca de uma
demonstração de uma conjectura de Morley ("a
função de espectro de uma teoria de primeira ordem
contável completa T é não-decrescente sobre
cardinais incontáveis"). A demonstração de Shelah
foi construída ao longo de quase 15 anos e é o principal
tópico de seu enorme tratado sobre Classification theory.
O tema predominante no livro de Shelah concerne a busca de
subconjuntos de um modelo de uma teoria estável sobre o qual
a dependência bifurcante é suficientemente boa a ponto
de admitir uma teoria de dimensão.
A Teoria Geométrica da Estabilidade (concebida por Ehud Hrushovski em
1987) estuda a estrutura fina de modelos de teorias estáveis.
Um tema sempre presente é a existência e a estrutura de grupos
definíveis.
Uma exposição profunda da teoria e de suas
aplicações fundamentais à teoria da
classificação foi realizada por Anand Pillay em seu livro
Geometric Stability Theory (1996).
Nos últimos anos têm-se observado o surpreendente sucesso da
aplicação da teoria a várias outras áreas da
matemática, tal como, por exemplo, geometria diofantina.
As principais ferramentas utilizadas na Teoria Geométrica da
Estabilidade são, essencialmente: geometrias, ortogonalidade,
modularidade, grupos estáveis.
Recentes desenvolvimentos, sobretudo a partir de um artigo do próprio
Shelah ("Simple unstable theories",
Ann. of Math. Logic 19(1980):177-203), fornecem um ferramental
bastante útil para o estudo de modelos finitos, principalmente
o conceito de "teorias simples" (grosso modo, as teorias nas quais
não se pode definir ordem parcial com uma cadeia infinita),
permitindo inclusive a
simplificação de algumas das construções
originalmente desenvolvidas por Shelah (ver recente survey
"From Stability to Simplicity", de B. Kim e A. Pillay, Bulletin of Symbolic Logic 4(1998):17-36, e o livro de F. Wagner: Simple Theories, Kluwer, 2000, ISBN: 0-7923-6221-7).
Teses e Dissertações Concluídas
Doutorado
Complexidade Descritiva de Problemas em Grafos
Haroldo G. Benatti
Março de 2000.
Teses e Dissertações em Andamento
Doutorado
Contributions to the investigations of Lascar strong types in simple theories
Steffen Lewitzka
Término: Abril de 2003.
Última atualização: 29 de Dezembro de 2004, 10:17:06 GMT-0300.
