Home Todos os Eventos Details - Eduardo Mucciolo (U. Central Florida): Entropias de Rényi e computação matricial

EMail Print

Todos os Eventos

Event 

Title:
Eduardo Mucciolo (U. Central Florida): Entropias de Rényi e computação matricial
When:
24.05.2013 11.00 h
Where:
Sala A5-01 - Niteroi
Category:
Seminários

Description

Seminários de Óptica e Informação Quântica

 

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.

Venue

Group:
Sala A5-01
Street:
Instituto de Física da UFF
ZIP:
24210-346
City:
Niteroi
State:
RJ
Country:
Country: br

Description

Sorry, no description available
<<  Jul 20  >>
 Su  Mo  Tu  We  Th  Fr  Sa 
     1  2  3  4
  5  7  811
121518
192225
2629