Data: Sexta-Feira 24/05/2013 Sala A5-01, 11:00

Palestrante: Eduardo Mucciolo (University of Central Florida, EUA)

Título: Entropias de Rényi, problemas de contagem, e computação matricial

Resumo: Contar o número de possíveis soluções de expressões booleanas está entre os problemas computacionais mais difíceis que se conhece, mesmo quando se deseja apenas uma contagem aproximada. Neste seminário, eu descreverei uma proposta de se usar emaranhamento, um conceito proveniente da teoria de informação quântica, para estabelecer a dificuldade computacional de resolver problemas de contagem. O emaranhamento e' medido pelas entropias de Rényi, as quais são obtidas a partir da bipartição do sistema de variáveis booleanas referentes ao problema. Essa proposta é testada na prática através de um esquema de computação numérico bastante eficiente baseado numa representação matricial das variáveis booleanas para o problema #2SAT. Tanto o método matricial quanto as implicações desses resultados para a teoria de complexidade serão discutidos.

~~LINKBACK~~ ~~DISCUSSION~~