Research questions for prof. Kristos's lecture:

What is a decision problem?

A decision problem is a problem whose solution is either yes or no given some input values. In other words, it is a problem that can be posed a yes/no question.

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

That there is a alogorithm that can solve the problem.

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

Class P is all decision problems that a sequential deterministic machine can solve in an amount of time that is polynomial in the size of the input. Class NP is all decision problems that can be solved in polynomial time on a non-deterministic machine.

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

Whether every problem whose solution can be quickly verified can also be solved quickly.

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

1 million $.

References