Professor Christos: Theory of Computation

1. What is a decision problem?

In computation theory, a decision problem is essentially a problem that can be presented as a yes or no question, where an algorithm takes the input values to then output yes or no.

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

If a decision problem is decidable, this means that it can be solved by an algorithm–the number of steps required to solve the problem being finite and–consequently–the time required to solve it is finite.

3. What is the class P? What is the class NP?

Class P is the set of problems whose time required for a solution is directly proportional to the number of elements involved, while class NP refers to the set of problems whose time required for a solution is not proportional to the number of elements.

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

The P versus NP problem essentially asks whether every problem which can be verified quickly is also solvable quickly–where the P versus NP question intuitively means possible vs. not possible.

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

As one of the seven Millennium Prize Problems, solving the P versus NP question would make someone $1,000,000 richer, where the Clay Mathematical Institute is willing to provide that amount to the first person who can solve it.