The Aged P versus NP Problem

Why is P=NP such a big deal that it warrants a $1 million prize?

Photo by Helloquence on Unsplash

P versus NP. Is it even solvable?

It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution. It is the most recently conceived problem of the seven (in 1971) and also the easiest to explain (hopefully).

What is it all about?

Before we deep dive, I hope it is safe to assume that those who clicked this article have some background in programming and some idea about algorithms and their run-time (time and space complexity). I will not go into huge detail regarding the technical details but provide some background to those non-technical folks out there.

Essential ideas to know for the non-programming folks

(Those familiar with time and space complexity can skip this section)

• Algorithms are basically just a set of instructions written in a programming language
• Algorithms are the ‘brains’ behind computer programs — they essential help solve our day-to-day problems such as vehicle routing, protein folding, sorting, finding prime numbers…