EDICIóN GENERAL

Yaroslav Shitov: Un matemático ruso desmiente una conjetura con más de medio siglo de vida

Menudas erratas.

<<Por tanto, si encontramos un algoritmo que resuelva de forma eficiente el problema de colorear grafos (con una cantidad de operaciones menor que un cantidad relacionada con el número de vértices del grafo), podemos ir al instituto Clay y reclamar un millón de dólares, porque habremos demostrado que P es distinto a NP, y con ello uno de los célebres problemas del milenio y que llevan asignado ese premio. Si alguno de los lectores tiene el algoritmo pero no entiende por qué implica que P es distinto de NP, los autores de este artículo se brindan a aclarar las dudas. Compartiendo parte del premio, claro está.>>

Primero, para que sea eficiente, la cantidad de opciones tiene que ser menor que un número relacionado polinomicamente con el número de vertices (o de aristas)... no te puedes saltar el polinomicamente, si no 2^|V| también vale y el algoritmo sería exponencial.

Segundo, lo que estarías probando sería que P = NP, ya que estarías encontrado un algoritmo polinomial (eficiente) para un problema NP-Completo (representante universal de la clase NP).

menéame