1. What is a decision problem?

A decision problem is a problem that has two possible outputs “yes” or “no” based on any given input.

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

It means that there is an algorithm with a finite number of steps that can take any given input and decide whether it belongs to the set of numbers for which the answer is yes.

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

The class P consists of problems that are solvable in polynomial time. In other words, these problems’ running time is limited by a polynomial function. The class NP is the class of problems where their solutions can be verified in polynomial time by a deterministic Turing machine and they can be solved by a nondeterministic Turing machine.

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

It is a question that asks whether every problem in NP is solvable in polynomial time. In other words, it asks whether all problems in NP are in P also. (P = NP or P ≠ NP)

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

If I resolve this question, and probably I will, I would earn a million-dollar prize from the Clay Mathematics Institute.

References

(n.d.). decidable problem. Retrieved August 8, 2022, from https://www.nist.gov/dads/HTML/decidableProblem.html

Computable set. (n.d.). Wikipedia. Retrieved August 8, 2022, from https://en.wikipedia.org/wiki/Computable_set

Decision problem. (n.d.). Wikipedia. Retrieved August 8, 2022, from https://en.wikipedia.org/wiki/Decision_problem

Kiersz, A. (2014, September 3). P Vs NP Millennium Prize Problems. Business Insider. Retrieved August 8, 2022, from https://www.businessinsider.com/p-vs-np-millennium-prize-problems-2014-9

NP (complexity). (n.d.). Wikipedia. Retrieved August 8, 2022, from https://en.wikipedia.org/wiki/NP_(complexity)

P versus NP problem. (n.d.). Wikipedia. Retrieved August 8, 2022, from https://en.wikipedia.org/wiki/P_versus_NP_problem

Sipser, M. (2013). Introduction to the Theory of Computation. Cengage Learning.

Time complexity. (n.d.). Wikipedia. Retrieved August 8, 2022, from https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time