2 ms·
At least in section 2, the biggest way you're deluding yourself is in assuming that you can extract a small number of candidate solutions from the problem. If y
by tsimionescu 3y ago
At least in section 2, the biggest way you're deluding yourself is in assuming that you can extract a small number of candidate solutions from the problem. If you actually work on any of the NP-complete problems you'll quickly realize that they have huge numbers of candidate solutions which are wrong. So, to find a true solution, you have to apply the solution verification algorithm (the one in P) a great many times, leading to the all known algorithms being super-polynomial.
More generally, you seem to think that problems in P and those in NP are considered unrelated. In fact, for all of the NP-complete problems (SAT, Travelling Salesman, knapsack etc) verifying a single candidate solution is a problem in P. However, the best known algorithms for solving the full problem are to iterate over all candidate solutions and run the P algorithm for each - which is exponential time or worse for all of these problems.
To find a P algorithm that solves one of the NP-complete problems, you need to find an idea that is better than just trying solutions to see if they fit.
- bionhoward 3y agoThank you!