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