La Encuesta P=?NP
No voy a entrar a explicar el problema P=?NP porque es de sobra conocido y no soy la persona más indicada para esa tarea pero llevo años pensando en escribir una entrada explicando mi posición al respecto. Sin embargo, no tengo ningún argumento científico para defender mi postura, que solo puede calificarse como fe religiosa más que como opinión lógica.
Afortunadamente, me han hablado de una encuesta que se realizó a cien eminentes investigadores que revelaban su opinión al respecto. Esta encuesta se publicó en 2012 pero la falta de avance en un problema tan atractivo que daría fama mundial al que lo resolviera (y un 1M USD) demuestran que no está ni mucho menos obsoleta.
La pregunta principal, en qué dirección se resolverá el problema, muestra la mayoría aplastante de 61 votos a favor de P≠NP mientras que solo hay 9 expertos convencidos de la igualdad de las clases.
Sobre la opinión concreta de los encuestados, me gustaría rescatar la de dos sospechosos habituales:
John Conway: (P≠NP) In my opinion this shouldn’t really be a hard problem; it’s just that we came late to this theory, and haven’t yet developed any techniques for proving computations to be hard. Eventually, it will just be a footnote in the books.
Donald Knuth: It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P=NP because there are only finitely many obstructions to the opposite hypothesis”; hence there will exists a polynomial time solution to SAT but we will never know its complexity!
Dejando de lado a tan insignes personalidades, hay muchas opiniones sobre las que reflexionar y he recogido a modo de resumen las que me han parecido más interesantes:
Mike Robson: (P≠NP) Maybe the question will be obsolete when we all have quantum computers.
Anonymous1: Only a few people will follow the proof. Whoever does will spend the rest of his life convincing people it is correct.
Richard Chang: (P≠NP) In the year, 2066 the idea that computers will double in speed every 18 months (Moore’s Law) has been ludicrous for 50 years. As such, no one uses asymptotic analysis anymore. Programs are written in assembly language to shave the running time. Some poor assistant professor will prove that P≠NP and fail to get tenure for it.
Harvey Friedman: (P≠NP) Detailed combinatorial work on easier problems, leading up to the full result.
David Isles: My guess is that the problem will be resolved not thru the development of new techniques but as a consequence of quite radical revisions in our way of conceiving of certain mathematical ideas. Such revisions will include an abandoning of the belief in a set of natural numbers unique up to isomorphism plus a recognition that there must be a more careful use of induction in reasoning about “natural numbers.” One consequence of this would be the recognition that exponential is, in gen
Sariel Har-Peled: (P≠NP) There are good reasons to believe the question is NOT relevant. In particular, assume that tomorrow I came up with a A(10) ∗ n time algorithm for solving SAT […]. It is completely useless, as this implies that the problem can not be solved for any reasonable size instance, although P=NP. […] so… Why is this question so important?
Vladik Kreinovich: (P≠NP) […] However, it is also highly possible that P will be proven to be equal to NP —but without the ability of solving all problems from NP easily, […] because the coefficients of the corresponding polynomial P(n) will likely be on un-physical (like 1040 or more).
Karl Papadantonakis: […] Clearly these are just quick opinions. Nobody really knows.
Por último, mi opinión, que curiosamente coincide exactamente con la de un tal Richard Karp de la Universidad de Berkeley:
Richard Karp: My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.
Además, Si los investigadores pensaran realmente que P=NP intentarían demostrarlo, ya que resolver cualquier algoritmo en tiempo polinomial (aunque puede ser un polinomio inviable) es suficiente incentivo, pero saben que no es así. La demostración de la desigualdad es un callejón sin salida que no ofrece ninguna aplicación matemática posterior y solo sirve para ganar un premio y un par de medallas. Puede que no sea la mejor justificación… de hecho, es embarazosamente cutre, pero es lo que pienso.
