A decision problem is a problem that can be phrased as a yes/no question. Specifically, it involves determining whether a given input satisfies a particular property or condition.
A decision problem is when there exists an algorithm that will provide a correct yes/no answer for every possible input in a finite amount of time. In other words, there’s a systematic method to solve the problem.
The class P consists of decision problems that can be solved in polynomial time. This means there exists an algorithm that can determine the answer to the problem in a time that grows polynomially with the size of the input.
The class NP consists of decision problems for which a given solution can be verified in polynomial time. All problems in P are also in NP, but it’s not known whether all NP problems can be solved in polynomial time.
The P versus NP question asks whether every problem for which a solution can be quickly verified (NP) can also be quickly solved (P). In other words, it questions whether P = NP or P ≠ NP. If P = NP, it means that for every problem where we can check a solution efficiently, there is also a way to find that solution efficiently.
Resolving the P versus NP question could lead to a 1 million dollar prize and other awards by various institutions.