Mais um P=NP…

Parece que ultimamente isso já está virando rotina, alguém sempre vem com uma descoberta fantástica de que P=NP…não foi diferente no caso do russo Vladimir Romanov, ele conseguiu um algorítmo que rode o problema do 3-SAT em tempo polinomial. Se não tiver falhas, isso realmente prova que P=NP, já que bastaria traduzir um problema NP para o 3-SAT e resolver com o algoritmo dele, porém atenção, não é por que o algoritmo roda em tempo polinomial que ele é rápido e vai acabar com a criptografia mundial ;).

Enfim, para quem realmente se interessa por essas coisas e quer estudar a fundo o algoritmo dele, pode ver no blog dele, e o código aqui. Mas já aviso que não é a coisa mais simples do mundo.

About Zarnick

Programer, sysadmin, guitarrist, and Italian. That's what I am. Plain simple.
News , , ,