Theory of Computation

What is a decision problem?

A decision problem is a problem that outputs YES or NO from an algorithm with given inputs. For example, the question "Is 31 prime?" would be a decision problem, as you need to have an algorithm to check if 31 is prime, and then output YES or NO.

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

For a decision problem to be decidable, it means that there needs to be an algorithm with an input that can output YES or NO in a given amount of time. If it cannot be solved in a given amount of time, it is considered undecidable.

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

The class P stands for polynomial time, which denotes the time that deterministic machines, such as human-made computers, can solve problems. In contrast, the class NP stands for Non-deterministic polynomial time, which denotes the time that non-deterministic machines solve problems.

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

The intuitive meaning of the "P versus NP" problem examines the issue that if a solution to a problem can be quickly verified, then it should also quickly be solved. It looks at polynomial time (P) and non-deterministic polynomial time (NP) to answer if a verification in polynomial time means a solution in polynomial time.

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

If you resolved the P versus NP question, you would be $1,000,000 richer, as the Clay Mathematics Institute selected this question as one of the seven Millennium Prize Problems, indicating that it is an everlasting and important problem in computer science.

References

If you want to learn more about the theory of computation, check these links:

"Decidability." Stacks Documentation, Gitbook, 2 Mar. 2024, https://docs.stacks.co/concepts/clarity/decidability. Accessed 15 Sep. 2025.

"Decision problem." Wikipedia: The Free Encyclopedia, Wikipedia, 19 May 2025, https://en.wikipedia.org/wiki/Decision_problem. Accessed 15 Sep. 2025.

"P, NP, CoNP, NP hard and NP complete | Complexity Classes." GeeksForGeeks, Sanchhaya Education Private Limited, 23 Jul. 2025, https://www.geeksforgeeks.org/dsa/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/. Accessed 15 Sep. 2025.

"P versus NP problem." Wikipedia: The Free Encyclopedia, Wikipedia, 15 Sep. 2025. https://en.wikipedia.org/wiki/P_versus_NP_problem. Accessed 15 Sep. 2025.