Theory and Algorithms
What is a decision problem?
It is an algorithm or function that only answers ‘yes/no’ or ‘true/false’ questions. An example of a decision problem is “given two sets x and y, is x a subset of y?”
What does it mean for a decision problem to be decidable?
A decision problem is said to be decidable if there is an effective procedure or method (recursive or non-recursive) that eventually halts at the correct answer within a finite amount of time.
What is the class P? What is the class NP?
- Class P (stands for Polynomial Time): It is a class of decision problems that can be solved in polynomial time by a deterministic machine.
- Class NP (stands for Non-deterministic Polynomial Time). It is a class of decision problems that can be solved by a non-deterministic machine in polynomial time (the solution can also be easily verified by a deterministic machine in polynomial time).
What is the intuitive meaning of the “P versus NP” question?
Whether or not a problem with a quickly verifiable solution can also be quickly solved. For e.g., since a Sudoku board state can be quickly verified to be correct, does that imply there is a quick and efficient algorithm to find a solution? So far, nobody could resolve this problem.
If you resolve the P versus NP question, how much richer will you be?
It is a part of the Millennium Prize problem set in which if any question is solved by someone, that person would be a million dollars richer.
Resources