**What is decision problem****What does it mean for a decision problem to be decidable?****What is the class P? What is the class NP?****What is the intuitive meaning of the “P versus NP” question?****If you resolve the P versus NP question, how much richer will you be?**

In computational complexity theory, a problem in which the answer id either Yes or No is called decision problem

A decision problem is said to be decidable or can also be said to be effectively solvable if the set of inputs for which the answer is yes is a recursive set.

In the field of CS, the P versus NP problem is a major unsolved problem which asks whether every problem that can be solved quickly can also be quickly verified.

The class of questions in which an answer can be provided using an algorithm in polynomial time is class P question. Again if we cannot find the answer quickly, but if we can provide enough information regarding the answer, it is possible to verify the answer quickly. Such type of questions be verified in polynomial time is known as class NP question. In order to find the answer to the “P versus NP” question, we need to determine whether problems that can be be solved in polynomial time can also be verified in polynomial time.

If anyone is successful in resolving the P versus NP question, he will make at least a million dollars, and perhaps much more.

Decidability (logic)URL

Decision ProblemURL

P vs NP URL

Prize moneyURL