Theory of computation

What is a decision problem?

Decision problems are problems that can be answered by yes or no depending on the input.

What does it mean for a decision problem to be decidable?

Decision problems can be solved by an algorithm that stops in all the inputs for number of steps.

What is the class P? What is the class NP?

Class (P) is a class that contains all the problems that can be solved on a deterministic sequential machine in a polynomial in the size of the input.

Class(NP) is a class that contains problems that can be without using the deterministic sequential machine.

What is the intuitive meaning of the “P versus NP” question?

(P) is a set of easy problems, whereas (NP) is a set of hard problems.

If you resolve the P versus NP question, how much richer will you be?

If you resolve a P versus NP question you will be a million dollars richer.