It is a problem whose output is always either “yes” or “no.”
A decidable problem refers to a problem for which there exists an algorithm that always produces the correct answer and solves the problem.
Both P and NP are classes of decision problems. P problems are those that can be solved by an algorithm in polynomial time. NP, which stands for nondeterministic polynomial time, refers to problems for which a given solution can be verified in polynomial time, even if finding that solution may take much longer, potentially exponential time.
The P versus NP question refers to the dilemma of: if a problem has a solution that can be verified in polynomial time, can it also be solved in polynomial time? In other words, it wonders whether problems that are easy to verify are also easy to solve.
The P versus NP problem is described as one of the most important mathematical problems that, if solved, could revolutionize the field of computer science. Thus, in 2000, the Clay Mathematics Institute in Cambridge, Massachusetts, designated it as one of the Millennium Prize Problems, offering a reward of one million dollars to anyone who successfully solves it.