Transmissões

Data

COLÓQUIO - IFUSP: Complexidade computacional, probabilidades e transição de fase

Normal Expandido
Formato
Reportar Erro
Denunciar
Incorporar
Recomendar
Download
Gostei
189 visualizações
Publicado em Fri Sep 01 08:05:06 BRT 2017
Formatos:  MP4 (480 X 360 px)
Responsáveis:  Luiz Cezar Galizio
Produção:  Luiz Cezar Galizio
Palestrantes:  Prof. Dr. Marcelo Finger

Existe um fenômeno empírico em computação de mudança de fase, o qual está associado a problemas NP-completos. Há uma conjectura, feita por Cheeseman em 1991, de que todo problema NP-completo está associado a este tipo de mudança de fase que, embora não haja até hoje uma demonstração matemática da validade desta conjectura, foi verificada em diversas classes de problemas NP-completos. Neste trabalho iremos descrever o fenômeno empírico da mudança de fase, seu aparecimento em diversos contextos e a forma como a robustez deste fenômeno tem guiado pesquisas na área de algoritmos para problemas NP-completos.