3 ms·
P vs NP is more about verifying correctness of a solution compared to the hardness of finding a good one. I don’t think interpolation/extrapolation fits very we
by maxov 6y ago
P vs NP is more about verifying correctness of a solution compared to the hardness of finding a good one. I don’t think interpolation/extrapolation fits very well.
However, what fits better is understanding existing ideas and verifying they indeed solve a problem, compared to the hardness of finding a “best solution” to a given problem. This is still only a rough parallel. You are right that many (probably most) complexity theorists believe that hardness separation in this case is a fundamental principle reflective of real life.