Assignment 4: Theory Research
What is a decision problem?
A decision problem is a yes-or-no question one can ask about some input that can be solved by an algorithm. For example, "Is this number prime?".
What does it mean for a decision problem to be decidable?
It means there is an algorithm that can always answer the problem in a finite amount of time.
What is the class P? What is the class NP?
P here stands for "polynomial". The problems that belong to class P can be solved in a polynomial amount of time (for instance, O(n²), O(n³)), i.e. fairly quickly. NP stands for "nondeterministic polynomial" and refers to problems that so far cannot be solved in a polynomial amount of time but can be verified as correct in a polynomial time. A common example of NP asymptotic is an exponential asymptotic (e.g. O(2ⁿ)). An example of an NP problem is a travelling salesman problem, which so far can be solved only in O(n*2ⁿ).
What is the intuitive meaning of the "P versus NP" question?
Both P and NP problems can be verified in a polynomial (i.e. quick) time. However, what distinguishes the two is how quickly we can SOLVE the problem. If we can solve it fairly quickly (in polynomial time), then it is P, but if we cannot, then it is NP.
If you resolve the P versus NP question, how much richer will you be?
Solving the P versus NP question guarantees you a $1 million prize from the Clay Mathematics Institute. You can also get much more money from patenting the revolutionary algorithm that you created.