P != NP

Hace dias que se anunció que un investigador serio de HP había probado que P != NP. Mucha gente (experta como aficionados) ya han empezado a discutir la demostración de más de 100 páginas . El chiste es que ha sido interesante todo aquello que ha surgido alrededor de esta prueba (que por cierto no es el primer intento serio). Para quienes quieran leer una crónica interesante al respecto pueden leer este blog(de un experto en el área). Pongo parte de la misma:

Last Sunday I planned to relax and read a book when I made the mistake of checking my email—never check your email on a Sunday. Among the usual messages was one from the eminent logician Harvey Friedman. It contained an attachment from Vinay Deolalikar, a researcher at Hewlett-Packard Labs in Palo Alto. The attachment was a 100+ page paper that looked serious, was serious, and had the elegant and short title "P≠NP." In addition, the email contained a quote from Steve Cook on Deolalikar's , which said,

"this looks like a serious effort."

Steve is a Turing awardee, a winner for discovering the very same P≠NP problem. He—a logician at heart—is very careful, and for him to say the word "serious" made it clear that I would not be relaxing nor reading any book that Sunday. I would be working hard to try and figure out whether this was really a serious effort or not.

I write a blog, along with about 126 million people who do the same. Mine is on complexity theory, and so this claim was something that I felt I needed to write about. There are several other blogs on complexity theory: the best and most famous are Scott Aaronson's, Lance Fortnow and Bill Gasarch's, and Terence Tao's. Even though I knew they would be discussing Deolalikar's paper, I felt I could not avoid getting involved—my blog after all has "P=NP" in its title.

My Sunday was gone, and as it turned out, so was the rest of the week. I kept reading the paper, sending and getting emails, and writing posts: all in an effort to report on what the theory community was doing to understand the claimed proof. Was the famous P≠NP problem actually solved? What did this mean for the field? And who cares anyway?

Perhaps the biggest surprise was that a lot of people do care. One lesson we learned is there are hundreds of thousands of people who were interested, there were hundreds of people who were willing to write thoughtful comments, and there were a number of superstar mathematicians and theorists who were willing to work hard to get to the truth of what Vinay Deolalikar claimed.