teste Tag Archives: complexidade computacional

Hermann aliou ciências exatas e humanas para resolver problema de 40 anos na computação

Pesquisador apresentou prova completa da resolução em live nesta sexta-feira (18)

A união entre as ciências exatas e humanas foi o caminho para a prova completa de  um problema de complexidade computacional que estava há mais de 40 anos em aberto. Nesta segunda live da série do Departamento de Informática da PUC-Rio, o professor Edward Hermann mostrou o resultado de um trabalho de pesquisa de 10 anos, no seminário “Compressão da provas lógicas e a conjectura NP=PSPACE”.

“Não sou mais assim, mas a gente, de exatas, normalmente menospreza a área de humanas. E isso é um crime, porque este resultado só existe graças a essa área e ao trabalho que eu tenho com o colega da Filosofia, o Luis Carlos Pereira. Ele foi meu professor e me ensinou tudo isso”, afirmou Hermann, no seminário nesta sexta-feira (18).

A pesquisa do professor do DI da PUC-Rio impactou o mundo da computação e era grande a expectativa de pesquisadores, professores e alunos para conferir a prova completa a que ele chegou, ao lado do pesquisador Lew Gordeev, da University of Tübingen. Durante a live, o professor recebeu elogios pelo ótimo trabalho e pela didática na apresentação.

Partindo da resolução de binômios de segundo grau – que se aprende no Ensino Fundamental -, Hermann apresentou o método teórico de sua pesquisa, aplicando o teorema da redundância para comprimir provas, e mostrou o passo a passo de como chegar ao CoNP=NP. “Finalmente, conseguimos provar a igualdade dessas duas classes”, disse. Depois da explicação, resumiu em poucas palavras sua descoberta com a pesquisa. “Se eu tenho uma prova muito grande, tem de ser redundante. E, se é redundante, pode ser reduzida.”

A palestra de Hermann está disponível no canal do DI do YouTube, assim como a de Hélio Lopes, que falou sobre Ciência de Dados, na estreia da série de lives do Departamento. Na próxima sexta (25), o professor Marco Antonio Casanova fará o seminário “Selected Topics on the Web-of-Data and Data Integration”. Não perca!

Hermann apresenta pesquisa que impressionou o mundo da computação, nesta sexta (18)

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!