Demystifying P, NP, and EXP

Today, we're going to talk about three mysterious terms you might have heard before:- P, NP, and EXP.

This is also important to understand them as using these you will know what all AI can or can't do, why your digital transactions are safe so far, why AI solutions are associated with GPUs or what makes it difficult to have lighter size AI models or why Amazon is never able to predict with last minute accuracy when will your package arrive, yet. Understanding them is important as helps you appreciate the power and limitations of computers.

Don't worry if they sound complicated—we're going to break them down and explain them in a way that's easy to understand. We are starting this new section, in simple words, to occasionally write concepts in simple words which someone with no background in this scientific concept can understand enough to get started in the domain.

Now back to the topic at hand:

P: Problems with "Quick" Solutions

First, let's start with P. P stands for "Polynomial-time," and it's a class of problems that can be solved "quickly" by computers. By "quickly," we mean that as the size of the problem grows, the time it takes to solve the problem doesn't grow too fast. In other words, these problems have a reasonable solution time.

Example 1:Imagine you have a list of numbers and want to find the largest one. A computer can do this relatively quickly by comparing each number to the others. This is an example of a problem in P.

Example 2: Determining if a number is even or odd is a problem in the P class. We can easily perform this operation by checking if the number is divisible by 2. This operation takes a constant amount of time, regardless of the number's size.

So if we make a table and the difficulty to validate a solution, it will look like this: