What is a decision problem?
A decision problem is a set of questions, each having either "yes" or "no" answer. This computational problem refers to finding an algorithm or repetitive procedure that will yield a definite answer.
What does it mean for a decision problem to be decidable?
A decision problem is decidable if it can be solved by an algorithm that halts on all inputs in a finite number of steps. A totally decidable decision problem is algorithmically solvable if the set of inputs for which the answer is yes is a recursively enumerable set.
What is the class P? What is the class NP?
Class P are a set of problems that can be solved in polynomial time by deterministic algorithms whereas, Class NP are problem sets that can be solved in non-deterministic polynomial time. They deal with the efficiency of algorithms.
What is the intuitive meaning of the “P versus NP” question?
The P-versus-NP problem is important for deepening our understanding of computational complexity and the intuitive question behind "P versus NP" is whether every problem whose solutions are easy to verify (NP) can also be solved efficiently (P) or if there are fundamentally hard problems in NP that cannot be solved quickly. Essentially, it asks whether there exists a shortcut or more efficient algorithm for all problems in NP, or if some problems are inherently complex and no efficient algorithm exists for them.
If you resolve the P versus NP question, how much richer will you be?
The P-versus-NP problem is one of the Millennium Prize Problems that warrants a $1 million prize. Solving this problem would have profound effects on computing, therefore, if one can prove or disprove its cryptically short equation, they would be a million dollars richer.
For more information, please visit:
MIT Medium.com Clay Math