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

EMail Imprimir

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
Categoría:
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

Grupo:
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
<<  Sep 20  >>
 Do  Lu  Ma  Mi  Ju  Vi  Sá 
    1  2  3  4  5
  6  7  8  9101112
131415161719
2021222326
27282930