Weekly Questions 2
1 - What is a decision problem?
- A decision problem is a computational question or problem that asks if a given input meets certain properties; e.g. given a natural number x, is x prime? The only possible outputs for a given input are Yes and No.
2 - What does it mean for a decision problem to be decidable?
- If a decision problem is decidable, it means that there exists an algorithm (known as a decision procedure) that can solve it (i.e. produce the correct output for every input) in a finite amount of time (i.e. it always stops and outputs Yes/No at some point).
- Conversely, an undecidable problem has no associated decision procedure that can solve it in finite time.
3 - What is the class P? What is the class NP?
- The class P (for Polynomial Time) is the group of decision problems that can be solved by a computer in an efficient, predictable, polynomial time.
- If a problem can be solved in polynomial time, it means that given an input length n, the time needed to solve it is n to some power.
- The class NP (for Non-deterministic Polynomial Time) is the group of decision problems where there is an efficient way to check the solution in polynomial time (regardless if it can be solved in polynomial time or not).
4 - What is the intuitive meaning of the “P versus NP” question?
- The P vs NP question asks if every decision problem where the solution can be checked in polynomial time can also be solved in polynomial time. It was conceptualized in 1971 by Stephen Cook and Leonid Levin independent from each other, and as of now is still unsolved.
5 - If you resolve the P versus NP question, how much richer will you be?
- The P vs NP problem is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute in Cambridge, Massachusetts; this means that if the P vs NP problem were to be resolved (either by proving or disproving it), the solver(s) would be given a bounty of $1,000,000 USD.
References & Websites