decision problems questions

1. What is a decision problem?

Answer: Essentially, a decision problem is a yes-or-no question that a computer has to compute on a specific input. So it always returns either true or false based on a certain algorithm that it was given to run on the inputted set of values

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

Answer: Decidable means that there is an algorithm that can solve the problem for any input in finite time. There are also undecidable problems, which basically means we know for sure there cannot possibly be an algorithm that could solve the problem

3. What is the class P? What is the class NP?

Answer: Class P stands for polynomial time, meaning a problem is easy enough for a regular computer to solve in polynomial time no matter how big the input. Class NP stands for non-determenistic polynomial time. That means it is very hard to find an algorithm to solve this problem, but if we do, it would be easy to check if it's true because it would take polynomial time.

4. What is the intuitive meaning of the “P versus NP” question?

Answer: To put it simply, the P versus NP question asks, if we can check a solution to a problem in polynomial time, can't we also find the solution in polynomial time?

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

Answer: Much much richer. At least by $1,000,000 from the Clay Mathematics Institute. You could buy about a half of a very small private jet

references:

• https://news.mit.edu/2009/explainer-pnp
• https://www.geeksforgeeks.org/dsa/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/
• https://xlinux.nist.gov/dads/HTML/decidableProblem.html
• https://www.claymath.org/millennium-problems/
• https://www.avbuyer.com/aircraft/private-jets