Quadro de avisos

====================================================
Seminário de Combinatória Extremal e Métodos Probabilísticos
====================================================


Título: Complexidade de espaço e expansores

Palestrante: Guilherme Oliveira Mota, UFC

Data: sexta-feira, 03 de outubro de 2008, 16:00

Local: Anfiteatro do NUMEC

Resumo: Sempre que pensamos em um algoritmo para solucionar
algum problema, logo vem a pergunta: Em quanto tempo este
algoritmo encontra a solução para o problema? Outra
abordagem interessante é analisar a quantidade de memória
necessária para execução do algoritmo. Dentre as classes de
problemas relacionadas à complexidade de espaço, podemos
citar a classe L, que compreende os problemas que podem ser
resolvidos deterministicamente utilizando espaço
logarítmico. Outra classe interessante é a classe SL, que
podemos descrever como o conjunto de problemas redutíveis ao
USTCON (Undirected ST-Connectivity: Dado um grafo e vértices
s e t, dizer se existe caminho entre eles) utilizando espaço
logarítmico.

Durante muito tempo, ficou sem resposta a seguite questão:
SL = L ? Em 2005, Omer Reingold respondeu afirmativamente
essa pergunta. A resposta foi obtida através de um
algoritmo polinomial para resolver o USTCON utilizando
espaço logarítmico. Para isso, Reingold utilizou o produto
Zig-Zag e as propriedades dos expansores. Discutiremos as
classes de complexidade de espaço e estudaremos como o
produto Zig-Zag foi utilizado para concluir que SL = L.