Within the computational theory, a decision problem is a yes-or-no question on specified sets of inputs. Essentially, a decision problem will answer these questions and will only give two outputs, which could be in the form of “yes or no,” “0 or 1,” etc.

A decision problem is called decidable when there is a decision procedure. This procedure determines the answer to the decision problem for every value in the set of its input. This decision procedure could be efficient or inefficient, but as long as it can solve the decision problem, the decision problem is decidable.

The class P stands for Polynomial Time. This class is the collection of decision problems that a deterministic machine can easily solve in polynomial time. Essentially, the solutions to the problems belonging to class P are easy to find practically and theoretically. This means that the decision procedure in class P can efficiently give a solution to this decision problem. Meanwhile, the class NP stands for non-deterministic Polynomial Time. This class is the collection of decision problems that a non-deterministic machine can solve in polynomial time. Essentially, the solutions to the problems belonging to class NP are harder to find, however, the solutions are easy to verify. The reason why NP problems are harder to solve is that there exist some problems in NP such that polynomial-time algorithms are not efficient enough to be able to solve, despite some prior extensive efforts.

The central idea of the “P versus NP” question is that can all problems that can be verified quickly also be solved quickly in polynomial time. This essentially means that, because class P contains all the problems that can be solved, some questions can’t be answered quickly unless provided with an answer, which can then be verified. With this, there comes the question of “P = NP?” The intuitive meaning behind all of this is to find if a problem can be both verified and solved quickly.

If you solve the P versus NP question, you will be rewarded a total of US$1,000,000. Good luck to any brave souls out there solving this, because that money is mine.