Theory

  1. What is decision problem
  2. In computational complexity theory, a problem in which the answer id either Yes or No is called decision problem

  3. What does it mean for a decision problem to be decidable?
  4. A decision problem is said to be decidable or can also be said to be effectively solvable if the set of inputs for which the answer is yes is a recursive set.

  5. What is the class P? What is the class NP?
  6. In the field of CS, the P versus NP problem is a major unsolved problem which asks whether every problem that can be solved quickly can also be quickly verified.

  7. What is the intuitive meaning of the “P versus NP” question?
  8. The class of questions in which an answer can be provided using an algorithm in polynomial time is class P question. Again if we cannot find the answer quickly, but if we can provide enough information regarding the answer, it is possible to verify the answer quickly. Such type of questions be verified in polynomial time is known as class NP question. In order to find the answer to the “P versus NP” question, we need to determine whether problems that can be be solved in polynomial time can also be verified in polynomial time.

  9. If you resolve the P versus NP question, how much richer will you be?
  10. If anyone is successful in resolving the P versus NP question, he will make at least a million dollars, and perhaps much more.


References:

Decidability (logic)URL

Decision ProblemURL

P vs NP URL

Prize moneyURL