Sam Ganzfried
Aug 13 · 5 min read

The P vs. NP problem has been singled out as one of the most challenging open problems in mathematics/computer science, and carries a $1M prize for the first correct solution. It is considered by many to be the single most important open problem in computer science. It was first discussed informally by John Nash, Kurt Gödel, and John von Neumann in the 1950s, and introduced formally by Stephen Cook in 1971. The problem has apparently stumped many brilliant minds, and incorrect alleged proofs are quite common. It is very clear that this problem is extremely challenging, and solving it would require concerted effort by an excellent mathematician (I would estimate approximately 10 years).

This leads to the question: who is an excellent mathematician who has both the ability to solve this problem as well as the incentive to spend the amount of time required? The most obvious candidate would be someone within the academic pipeline who specializes in computational complexity theory, perhaps at a university strong in CS theory such as MIT or Berkeley. Typically at leading research universities, a professor leads a laboratory of several students, who are funded by research grants, each working on a separate project. The professor splits his/her time between applying for these grants, advising, teaching, reviewing, serving on committees, giving invited talks, and various other administrative tasks. Typically the student is the lead author on most major projects, though occasionally professors can find the time to focus on one of their own projects.

Now, is P vs. NP going to be solved by a graduate student? There are many brilliant grad students, and I suspect that some could solve it if they dedicated an extended period of time specifically to it (my estimate above was approximately 10 years). However, I think it is extremely unlikely that a graduate student would have incentive to attempt this problem. To start, any prospective grad student who put on their application that they planned to solve the P vs. NP problem would immediately have their application thrown out, because this proposal appears outlandish and overly ambitious. Furthermore, assuming the student begins a PhD, it seems crazy to shoot for solving such a challenging problem that they could easily make no progress on for several years. Without any publications after several years it is likely the student would get kicked out of the program (or at least dropped by the advisor), and typically it is expected to produce a completed PhD thesis within 5–8 years in computer science. Regardless of whether a grad student would actually be able to solve the problem, it does not appear that they would have an incentive to even try. The situation is similar for a short-term postdoc, who is expected to publish several papers within a short duration of time.

Next let’s consider professors. A new assistant professor must simultaneously start growing a research laboratory, which must be funded from a steady source of grants, as well as the list of other tasks described above — teaching, advising, reviewing, committees, etc. In particular, an assistant professor typically needs to obtain significant amounts of funding from grants and regularly publish papers in order to obtain tenure. This leaves neither the time nor energy to start working on an ambitious major open problem that would involve many years of work with high chance of leading to no publications at all. All of this would need to be done “on the side,” as it is very unlikely that a grant proposal to solve this problem specifically would be funded.

Tenured professors are a bit of a different story, as they have guaranteed job security even after potentially long periods without publications or grants/students. However, they will still have at the least teaching and various other administrative obligations taking their time and attention. Furthermore professors in computer science often don’t get tenure until around age 40. While of course it is very possible to produce excellent work above age 40, it has been asserted that “mathematicians peak on average at 26.5 years of career age,” suggesting that it may be someone a bit younger whom would be most expected to achieve such a breakthrough mathematical result. (And furthermore tenured professors will likely have a degree of burnout after having spent the last decade chasing tenure that is unrelated to age directly).

So it does not appear that there is anyone along the academic pipeline who has essentially up to 10 years to dedicate fully to a major problem like this. Of course there is some chance that someone will happen to stumble into the solution by chance, but for a problem of this magnitude I would expect that there is no “simple/shortcut” solution and we would really expect that it would be solved by someone dedicating themselves to it for a long period.

These days there are also many researchers at industrial research labs, such as Microsoft, Google, Facebook, IBM, etc. However, I get the impression that often these researchers are focused on projects that will lead to increased revenue for the company, or at the least a steady stream of publications. I find it extremely unlikely that Facebook research would hire someone to work on P vs. NP for 10 years, potentially having nothing to show for the effort at all.

Regardless of whether it is feasible for anyone to actually solve with dedicated effort over a 10-year period, it is very challenging to think of anyone who has incentive to even try. It would have to be an extremely gifted mathematician who also had the financial and professional freedom to be able to spend 10 years working on it without any significant other obligations. (And according to the cognitive research preferably in their 20s or 30s.) My best guess would be someone who excelled at math in college, and then pursued a career either in finance or the tech industry and was able to earn enough money to retire at a young age. Then they could freely pursue their interests for an extended time without distractions, which is what would be required to solve a problem of this magnitude. Of course they would not be working on this for the prize money (it is unlikely for anyone to have incentive to spend 10 years working on a problem that they may never solve in hopes of the $1M prize), but really just for a pure recreational intellectual challenge, and fame if successful.

Ganzfried Gleans

AI, game theory

Sam Ganzfried

Written by

Researcher in artificial intelligence and game theory http://www.ganzfriedresearch.com/

Ganzfried Gleans

AI, game theory

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade