What is a decision problem?

A decision problem is a computational question consisting of an input which can only have a binary output answer, such as Yes/No or True/False. This is particularly relevant in computer science and mathematics, since these fields often include decision problems such as: Is the input n a prime number? or In this given list, is the number 129 present?

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

If a decision problem is decidable, it means that the problem can be answered with a single algorithm that provides a correct output for every valid input. This has to be done without exceptions and in a finite amount of time, without running into an infinite loop.

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

Class P stands for Polynomial Time. Problems in this category can be easily answered as well as checked by a computer. As the inputs get bigger, the time it takes for the computer to solve the problems grows at a manageable rate, such as n² or n³. An example of a class P problem is finding a specific item in an unorganized list: it’s quickly done and quickly checked.
Class NP stands for Nondeterministic Polynomial Time. Finding a solution to problems in this category is extremely challenging and lengthy for computers. However, once provided with an answer, NP problems can be checked quickly in polynomial time. An example of an NP problem is solving a Sudoku puzzle – completing the puzzle may take an extremely long time, but checking if the solution is correct can be done in seconds.

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

The P versus NP problem is a dilemma regarding whether or not every problem that can be easily checked, can be solved in an equally simple way; it asks if P=NP. This has a deep significance since it questions if problems we can comfortably check, but seem impossible to solve, have a hidden, unidentified simple solution. Furthermore, proving the relation would have major real-life consequences: reverse-engineering would be applied everywhere, and this could both significantly ruin and develop various fields.

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

If I solve the P versus NP problem (woah), I’d get $1,000,000 from the Clay Mathematics Institute. I would also completely reshape the fields of mathematics and computer science, and likely receive a Turing award. (not happening to me anytime soon)

Found this overview interesting? Hop onto these webpages to learn more!

A dictionary's in-depth definition of a decision problem
The Clay Mathematics Institute on the P vs NP dilemma
An excellent insight into class P and class NP problems