Professor Christos - Theory

What is a decision problem?

A decision problem is a type of computation which asks for a yes or no answer based on an input. This question can therefore be said to have a binary outcome for every possible input.

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

A decision problem is decidable if there is an algorithm which can solve a problem (hence give a yes or no) for every input and in a finite amount of time. Simply put, this is if a problem can terminate with the correct answer.

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

The class P refers to decision problems which can be solved in polynomial time. This means there is an efficient algorithm which will provide a solution relatively quickly.

The class NP refers to decision problems where, for problems where the answer is yes, the solution can be verified in polynomial time. This also includes problems which we don’t know if there is an efficient solution.

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

The P vs NP problem simply asks whether every problem for which a solution can be verified quickly can be solved quickly. This is the same as asking: “If it’s easy to check a solution, is it also easy to find one?”

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

If the P vs NP problem is resolved you would win 1 million dollars as it is one of the millennium prize problems. You would also gain immense respect and further opportunities for wealth.

References