Theory




What is a decision problem?


A decision problem something that can be expressed as a yes/no question based on specified inputs.



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


We can declare a decision problem as decidable if for every possible input, we get a definite yes/no answer in a finite amount of steps.



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


Class P is a set of relatively easy problems whose solutions can be found in polynomial time. On the other hand, class NP (nondeterministic polynomial time) is a set of harder problems whose answers can be verified in polynomial time, but cannot be solved in that time. It may take exponential time to solve NP problems.



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


The basic meaning it boils down to is if P = NP, then NP problems should also have a similar solution to that of P problems, due to which their solutions can be found relatively quickly.



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


It’s one of the seven millennium prize problems, so you get the US$1000000 prize money for solving it. That may only paltry compared to the fame you receive as the person who solved one of the hardest problems of mathematics, and the most important problem in computer science.