What is a decision problem?

It is the type of problem that asks a yes-no question on the entire range of inputs. The classical example is deciding whether a given natural number is prime or not.

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

The decision problem is decidable if it has a concrete yes or no answer. In other words, it is the problem that can be solved by an algorithm.

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

• Class P (polynomial time): it is a problem that can be solved by an algorithm in polynomial time (O(n**k) where k = const)
• Class NP (nondeterministic polynomial time): it is a problem whose answer can be easily (and quickly) verified but cannot be solved by an algorithm in polynomial time.

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

Meaning: Can a solution for any problem can be quickly verified as well as quickly solved?

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

FOR ONE MILLION DOLLARS! In 2000, the Clay Mathematics Institute offered $1,000,000 each for the solutions to 7 math problems that included "P versus NP" question. Since then, out of all 7 problems, only one has been resolved, which, fortunately, was not "P versus NP" problem.