2 ms·
If you have an algorithm with a worst case polynomial bound on the time it takes to solve an NP complete problem, then UPS, Fedex and other companies would pay
by carterschonwald 17y ago
If you have an algorithm with a worst case polynomial bound on the time it takes to solve an NP complete problem, then UPS, Fedex and other companies would pay nicely to use a service to optimally do scheduling, routing and resource allocation.
On the other hand, since it is more likely that P!=NP, this "almost" algorithm probably fails exponentially on some set of examples, and in practice there are plenty of NP complete problems which enjoy very good approximation algorithms or heuristic algorithms which work well for typical problem instances.
- carterschonwald 17y agoand if you in fact have a problem that shows P=NP, publish it so you can win the millenium prize, 1 million dollars plus ease at getting tenure so you can goof off is nothing to sneeze at
- zackattack 17y agoEven though the millenium prize may be the most obvious solution, your best option might be to monetize the discovery privately.
- neilc 17y agoAssuming that your solution is practical, which might well not be the case (O(n^c) is polynomial for any constant c).