A simple way to understand P / NP complexity
Believe it or not, this is important to understand how we can get to AGI!
The computers we have are universal computing machines. They solve problems that humans give them. But what is the requirement for solving problems thrown at them?
A bug-free algorithm that is created by humans. (this qualifier is a must until algorithms can be created by the computers themselves! - stay tuned for more posts about this in the future about artificial general intelligence)
The other thing computers do well - accurately and fast - is comparing and confirming if two things are equal or not. e.g. given two 1000-digit prime numbers and their product, they would be checked for accuracy in sub-seconds.
Now, we humans want to solve problems, this is in our nature.
For the ones that we can rely on computers to solve - accurately and quickly - what kind of problems are these?
There are problems that humans have figured out the algorithms for and then there are problems for there are no algorithms found (yet). And this is where the P and NP distinction comes in.
The set of problems we have algorithms for are P (Polynomial time) complexity problems. Everything from sorting a list of numbers to your Excel sheets, to the internet, everything that your computer/iPad/iPhone, etc. is doing right now is computing solutions for problems that fit in this set!
That is easy enough right?, okay, Now, how about NP problems? - Firstly, NP = Nondeterministic Polynomial time. The reason why the term, Nondeterministic is used is to do with something called Turing Machine (which is out of scope for this little writeup - read more on Wikipedia for this.). But to come back to what these types of problems are? - Simply stated, these are problems for which humans do not have solutions, hence no algorithms, no computer can solve any of these problems. Okay, well, but given an NP problem and its solution, computers can verify if the solution is correct or not. That is it. That is all that NP problems are! (Well, more or less1)
One example of an NP problem is finding prime factors for arbitrary large composite numbers. No computer with finite time and memory can find the prime factors, but, if it is given a composite number and the factors, it can quickly verify if the factors produce this composite or not. This property is what current cryptography is based on by the way.
Once we understand this basic difference, we can begin to dig more into what it takes to create algorithms that can run on computers, and why there are problems to which we humans don’t have solutions! Hint - human creativity.
More on that later, hopefully soon enough!
We are giving an intuitive description of these terms here - for current computers as they are in 2022. The probable solution to the question is P ?= NP has a prize set to $1M, so these are some of the most difficult meta-problems in themselves to think about and the math and philosophy about this goes deep.