Resultado alcançado em parceria com Lew Gordeev, da University of Tübingen, é tema da segunda edição da série de lives do DI
No universo da complexidade computacional, há problemas que permanecem por décadas sem solução. E um deles estava há mais de 40 anos em aberto, até que a pesquisa realizada pelos professores Edward Hermann, do Departamento de Informática da PUC-Rio, e Lew Gordeev, da University of Tübingen — uma das onze universidades alemãs do German Initiative for Excellence in Research —, conseguiu fechá-lo com uma prova completa.
Na sexta-feira (18), em live transmitida pelo youtube do DI às 15h, Hermann apresentará o trabalho, publicado no periódico científico “Bulletin of the Section of Logic”, que impactou a comunidade da área. No seminário “Compressão de provas lógicas e a conjectura NP=PSPACE”, o professor vai mostrar o resultado da pesquisa. “É um problema que ficou aberto durante algum tempo. Usamos as técnicas de uma área que veio da fundamentação da matemática e da filosofia e acabou parando na computação”, explicou.
O público poderá verificar ao vivo como a prova é validada na palestra, que relaciona diferentes temas, como a teoria da prova, lógica e algoritmos. “Ao conseguir mostrar que provas na lógica proposicional podem ser curtas sempre, você prova que CONP está dentro de NP. E a principal ferramenta para demonstrar isso foi perceber que provas grandes, que demandam muito tempo na verificação, têm seu grau de redundância proporcional ao seu tamanho”, disse Hermann.
Esta é a segunda semana da série de lives do DI, que estreou sexta (11), com o professor Hélio Lopes apresentando o seminário “Pesquisa em Ciência de Dados: A Escalada para a Valorização dos Dados”. O evento alcançou mais de 100 pessoas assistindo simultaneamente e segue disponível no canal do DI no Youtube. Não perca o próximo, dia 18 às 15h!