Q1: What is a decision problem?
a decision problem is a computational problem that can be posed as a yes–no question of the input values.
Q2: What does it mean for a decision problem to be decidable?
A decidable decision problem is a decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps.
Q3: What is the class P? What is the class NP?
P is set of problems that can be solved by a deterministic Turing machine in Polynomial time. NP is set of problems that can be solved by a Non-deterministic Turing Machine in Polynomial time.
Q4: What is the intuitive meaning of the “P versus NP” question?
If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?
Q5: If you resolve the P versus NP question, how much richer will you be?
At least 1 millon dollars