- A decision problem is a problem which can be answered with a ‘yes’ or ‘no’. Determining answer to the ‘Do you want to go to the park?’ question is a decision problem as well.
- If there is a problem for which we cannot approximate the exact time/complexity/iterations the problem will be solved. For example, it is impossible to answer with the exact time you can become a billionaire, although it is still possible
- Class P contains all the problems that can be solved within polynomial complexity, while NP class contains those problems which we can solve with verification of a certain answer in polynomial time. For NP, we may come to the right answer after verifying all the previous, not right, ones.
- The problems for which we can check in polynomial time if an answer to them is right or not, in case P=NP, are also fully solvable in polynomial time.
- Depends on my ethical part of personality and the way I have resolved the problem. If my proof to the solution is constructive, then I have a way to hack any bank account in the world (if I decide to do so). However, if I only proof that P is equal to NP or not, then I get not much from that, except for the prize of $1,000,000 promised for the problem.
https://www.youtube.com/watch?v=JfX7VK7ocRU
https://news.mit.edu/2009/explainer-pnp
https://www.claymath.org/millennium-problems/p-vs-np-problem