Data: 17/06/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: "Pebble games" e algumas aplicações em complexidade computacional
Palestrante: Susanna Figueiredo de Rezende (Czech Academy of Sciences)


Resumo: "Pebble games" são jogos definidos sobre um grafo acíclico dirigido. Na versão clássica existe um único jogador e, no início do jogo, o grafo não contém nenhum pebble. Em cada rodada o jogador pode colocar um pebble em qualquer vértice que tenha todos os seus antecessores com pebbles (em particular, sempre pode colocar um pebble em qualquer fonte) ou pode remover um pebble do grafo. O objetivo é colocar um pebble em cada vértice em algum momento do jogo minimizando o número total de pebbles simultaneamente no grafo.

Esse jogo simples está por trás de muitos resultados importantes em complexidade computacional. Um exemplo notório é a prova de Hopcroft, Paul e Valiant (1977) que DTIME(f(n)) está contido em DSPACE(f(n)/log f(n)). Outros exemplos mais recentes incluem diversas separações em complexidade de circuitos e trade-offs de espaço e tempo em complexidade de provas. Neste seminário, apresentaremos alguns resultados e problemas em aberto relacionados com "pebble games" e mencionaremos algumas das aplicações.