What is a decision problem?

It's a computational problem that involves answering a yes-or-no question after running a given input through an algorithm. For instance, "is the given input 10 a perfect square?" This question requires running 10 through an algorithm that returns either yes or no.

What does it mean for a decision problem to be decidable?

Unlike undecidable decision problems, decidable decision problems can be solved by an algorithm eventually, leading to a yes-or-no answer. An example of a decidable decision problem is finding whether an input number is prime or not. An example of an undecidable decision problem is the halting problem.

What is the class P? What is the class NP?

The P stands for polynomial time. This class refers to decision problems that can be solved by a deterministic machine in polynomial time. On the other hand, NP (or nondeterministic polynomial time) refers to the decision problems that can be solved by a non-deterministic machine in polynomial time.

What is the intuitive meaning of the “P versus NP” question?

It's the question of whether or not a decision problem can be solved in polynomial time when its verification happen in polynomial time. In basic terms, there are many NP problems that take a lot of time to solve, but once solved, validating their solution takes much less time than finding it.

If you resolve the P versus NP question, how much richer will you be?

I will receive millions of dollars in awards alone—like the one from the Clay Mathematics Institute. I can, alternatively, keep that knowledge a secret and become a sales consultant.