Título: A good matrix is hard to find

Palestrante: Everton Rufino Constantino

Sexta-feira 9 de novembro, Sala 1, 16h

O problema da submatriz é o de se encontrar uma submatriz, k1 x k2,
'grande' que possua uma propriedade Pi não-trivial e hereditária. Este
problema foi provado ser NP-difícil. Nesta apresentação mostraremos esta prova
e discutiremos algumas implicações em vários
problemas da computação.