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://xlinux.nist.gov/dads/HTML/decisionProblem.html
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://xlinux.nist.gov/dads/HTML/decidableProblem.html#:~:text=(definition),%2C%20algorithmically%20solvable%2C%20recursively%20solvable.
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.
https://www.youtube.com/watch?v=n0zd5hcOSQI
https://www.educative.io/answers/what-is-the-difference-between-p-and-np-hard-problems https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_p_np_class.htm#:~:text=P-Class,are%20called%20intractable%20or%20superpolynomial.

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

Haolin Wang

CMU-Q CS