## Prof. Christos/ Theory

1.What is a decision problem?
In computational theory, a decision problem is defined as a problem with a yes/no,true/false answer.
https://www.newworldencyclopedia.org/entry/Decision_problem
https://www.britannica.com/topic/decision-problem

2. What does it mean for a decision problem to be decidable?
A decision problem is considered to be decidable if it can be solved under a finite number of steps to stop all input and reach a valid conclusion.
https://en.wikipedia.org/wiki/Decidability_(logic)
https://cs.uwaterloo.ca/~a23gao/cs245_f17/notes/undecidability_solutions.pdf

3. What is the class P? What is the class NP?
In a P class, problems are solvable under polynomial time. While in an NP class, the problems can be verified whether they're true or false under polynomial time.

4. What is the intuitive meaning of the “P versus NP” question?
A P versus NP question pretty much asks that if a problem is verifiable, is it also solvable under a polynomial time.
https://www.quora.com/What-is-an-intuitive-explanation-of-P-NP
https://en.wikipedia.org/wiki/P_versus_NP_problem
https://bigthink.com/the-future/what-is-p-vs-np/

5. If you resolve the P versus NP question, how much richer will you be?
A million dollars richer, but later on I'll probably rival Jeff Bezos in terms of wealth.
https://bigthink.com/the-future/what-is-p-vs-np/
https://gizmodo.com/if-you-solve-this-math-problem-you-could-steal-all-the-1836047131
https://www.quora.com/If-I-solve-p-np-will-I-become-very-rich

Haolin Wang

Sarissa theme designed by iozcelik

CMU-Q CS