Pesquisador avança em um problema computacional após 35 anos sem solução — Universidade Tecnológica Federal do Paraná UTFPR
Você está aqui: Página Inicial > Notícias > Geral > Pesquisador avança em um problema computacional após 35 anos sem solução
Pesquisador avança em um problema computacional após 35 anos sem solução
Os estudos são de uma dissertação do mestrado em Ciência da Computação do Campus Ponta Grossa
publicado: 24/08/2021 09h30 última modificação: 24/08/2021 10h00
Estudos foram desenvolvidos durante uma dissertação de mestrado em Ciência da Computação do Campus Ponta Grossa (Foto: Decom)
Um trabalho da área da Teoria da Computação realizado durante a dissertação de mestrado em Ciência da Computação do Campus Ponta Grossa promete avançar em um problema matemático sem solução há 35 anos. Os estudos são do mestrando Luis Gustavo da Soledade Gonzaga, com a orientação das professoras Sheila Almeida (Campus Ponta Grossa) e Cândida Nunes Silva (UFSCar).
Luis Gustavo Gonzaga descreveu, em sua dissertação, que se a entrada para o problema for um grafo que pertence à interseção das classes intervalos e split, então há sim uma solução computacionalmente eficiente, respondendo parcialmente à questão colocada por Johnson em 1985.
Além disso, em outras pesquisas em conjunto com o aluno de doutorado do Instituto de Computação da UNICAMP, Jadder Sousa Cruz, eles também demonstraram que se a entrada for um grafo pertencente à interseção das classes de comparabilidade (do prêmio de US$ 1 milhão) e split, também há uma solução computacionalmente eficiente.