- What is a decision problem?
- A decision problem refers to a yes-or-no question with a specific set of input data.
- What does it mean for a decision problem to be decidable?
- If a decision problem is decidable, it means that:
- - it can be solved through the use of a corresponding algorithm.
- - it halts on any input that is provided after completing a finite number of steps.
- What is the class P? What is the class NP?
- Class P: problems that can be solved by a computer in a reasonable amount of time, known as polynomial time. As the length and complexity of a problem increases, the amount of time it takes to solve that problem also increases at a reasonable rate.
- Class NP: a solution can be checked quickly, regardless of how long it takes to determine that solution.
- What is the intuitive meaning of the “P versus NP” question?
- The solution of this question would answer if any problem's whose solution can be checked/verified quickly can also be solved quickly. The question aims to determine whether the 2 are fundamentally different or not.
- If you resolve the P versus NP question, how much richer will you be?
US$1,000,000
- It is one of the Millenium Prize Problems chosen by the Clay Mathematics Institute.
What is a decision problem
Geeks for Geeks, decidable decision problems
The Million Dollar Question: P = NP