3 ms·
My simplistic take away is it's an answer to this question about algorithms. For a problem you can have a number of different algorithms to solve the problem.
by Gibbon1 11y ago
My simplistic take away is it's an answer to this question about algorithms.
For a problem you can have a number of different algorithms to solve the problem. And a number of algorithms to check the solution to a problem. This is a point that is skipped over and trips lay people up because in school people are usually taught _the algorithm_ for solving a problem. But there are all sorts of ways to skin the cat mathematically. Some of these algorithms are great and some are 'bad'
Polynomial time algorithms are good. Ones that blow up exponentially are bad.
The question is, if you find a good polynomial time checking algorithm for a problem, does that mean there are polynomial time solving algorithms for that problem? Or not.
- Gibbon1 11y agoJust wanted to add, out of my butt I think the point not explicitly stated is, if you can prove P=NP then I think it means that you can also mechanically transform polynomial checking algorithms into polynomial time solving algorithms.