Theory of Computation Research
What is a decision problem?
In decision problems, input is processed through an algorithm and the answer could only possibly be true or false (it can be 0/1 or yes/no).
What does it mean for a decision problem to be decidable?
A decision problem is decidable when the problem can be solved correctly by an algorithm.
What is the class P? What is the class NP?
Class P: Polynomial Time
Decision problmes that are solvable in theory and practice.
Class NP :Non-deterministic Polynomial Time
Decision probolems that are harder to solve but easy to verify.
What is the intuitive meaning of the “P versus NP” question?
"P vs NP" aks if every decision problem that can be verified "quickly" can be solved "quickly."
If you resolve the P versus NP question, how much richer will you be?
