What is a decision problem?
is a question that can be answered in a simple yes or no
What does it mean for a decision problem to be decidable?
is when a decision problem has clear set of rules and steps like an algorithm that can be used to figure out whether the answer is yes or no
What is the class P? What is the class NP?
"P is the set of languages for which there exists an efficient certifier that ignores the certificate."(Source)
which means P is a set/list of a languages/decsion problems which can be solved by a decided upon number of steps/time.
"NP is the set of languages for which there exists an efficient certifier."(Source)
NP is the same however to get the number of steps/ time you need a certifcate which means it needs to check if an element is wiht in the given set
What is the intuitive meaning of the “P versus NP” question?
whether it is better to have a predetermined number of steps (P) or determine the number of steps during the process
If you resolve the P versus NP question, how much richer will you be?
the P vs NP question is a millennium prize problem meaning you will be awarded 1 million dollars upon completion
Refrences