Theory
-
Prof. Christos
What is a decision problem?
A decision problem is a problem where there is only two possible solutions, yes or no .
What does it mean for a decision problem to be decidable?
A decision problem being decidable means that it can be solved with an algorithm.
What is the class P? What is the class NP?
The class P is solvable decision problem in polynomial time.
The class NP is verifiable problems in polynomial time
What is the intuitive meaning of the “P versus NP” question?
P: easy problems.
NP: extremely difficult problems.
If you resolve the P versus NP question, how much richer will you be?
$1,000,000💰💰💰
Reference List:
https://www.geeksforgeeks.org/halting-problem-in-theory-of-computation/#:~:text=Decision%20problems%20%E2%80%93,solution%20to%20a%20particular%20problem%3F
https://xlinux.nist.gov/dads/HTML/decidableProblem.html#:~:text=(definition),%2C%20algorithmically%20solvable%2C%20recursively%20solvable.
https://en.wikipedia.org/wiki/P_versus_NP_problem#:~:text=In%20this%20theory%2C%20the%20class,be%20verified%20in%20polynomial%20time
https://xlinux.nist.gov/dads/HTML/decidableProblem.html#:~:text=(definition),%2C%20algorithmically%20solvable%2C%20recursively%20solvable.
https://en.wikipedia.org/wiki/P_versus_NP_problem#:~:text=In%20this%20theory%2C%20the%20class,be%20verified%20in%20polynomial%20time