Computational Theory

What is a decision problem?

A decision problem is a computational problem that can be answered with "yes" or "no" when given an infinite set of inputs. You can use an algorithm, which is called a decision procedure, to solve a decision problem.

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

A decision problem is decidable when you can use an algorithm (called a decision procedure) to answer with "yes" or "no". A computer should be able to compute the decision problem with an infinite amount of inputs, by using the algorithm you provided.

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

• Class P represents problems that can be solves and verified in polynomial time.

• Class NP represents problems where potential solutions can be checked in polynomial time, but not necessarily found. 

Polynomial time means when the algorithm run time is upper bounded by a polynomial expression in the size of the input for the algorithm. (Wikipedia contributors, Polynomial Time).

What is the intuitive meaning of the "P versus NP" question?

The "P versus NP" is a major unsolved problem. The intuitive meaning behind the problem is that it asks if "every problem whose solution can be quickly verified can also be quickly solved" (Wikipedia contributors, "P Versus NP Problem").

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

If you manage to solve the problem, you will become $1 million richer. 

Citations

Wikipedia contributors. “Decision Problem.” Wikipedia, 13 Aug. 2024, https://en.wikipedia.org/wiki/Decision_problem#:~:text=In%20computability%20theory%20and%20computational,given%20natural%20number%20is%20prime. (Accessed 24 Sep. 2024).

---. “P Versus NP Problem.” Wikipedia, 5 Sept. 2024, https://en.wikipedia.org/wiki/P_versus_NP_problem#. (Accessed 24 Sep. 2024).

P Vs. NP: The Million-dollar Question (Literally!). https://omp.com/blog/p-vs-np-the-million-dollar-question#:~:text=Computer%20scientists%20have%20been%20trying,can%20prove%20that%20P%20%3D%20NP. (Accessed 24 Sep. 2024).

---. “Time Complexity.” Wikipedia, 11 Aug. 2024, https://en.wikipedia.org/wiki/Time_complexity#:~:text=An%20algorithm%20is%20said%20to%20be%20of%20polynomial%20time%20if,for%20some%20positive%20constant%20k. (Accessed 24 Sep. 2024).