A scenario with two outcomes (yes or no) that a person (the decision maker) needs to choose from. The decision maker is made aware of what the scenario is, what limitations are set on the scenario and how the scenario is evaluated. An example of a decision problem would be: “given two integers a and b that are greater than 0, does that make a and b natural numbers?” Since this scenario describes the properties of the numbers a and b and asks the decision maker to pick if the numbers qualify as natural numbers or not.
A decidable decision problem is what you get when there is a set method that can be applied to the problem to achieve one of the two outcomes specified in the problem itself. This method you use is called the decision procedure or decision algorithm. Since you use an algorithm to determine decidability, you could consider this question as what makes a decision problem computable.
Class P problems refer to all decision problems that can be solved using Turing machines (hypothetical devices which manipulate symbols on a strip of tape based on a table of rules) called deterministic machines (machines with rule sets that only allow one action to be performed from any given scenario). These machines also solve the problems in polynomial time, which refers to the execution time of computing the problem being a polynomial function of the problem size: m(n) = O(n^k) where O = time needed, n = problem size or complexity of input for the problem and k = constant.
Class NP problems refer to decision problems that can be solved by non-deterministic machines in polynomial time. Nondeterministic machines have rule sets that allow for more than one action to take place for any given scenario.
It refers to the discussion of whether NP problems can be classified as P problems. Can be seen as hard NP problems having easy solutions like P problems did.
According to the MIT Technology Review, the reward for solving this with a verified proof gets $1 million.