3 ms·
There is no need for the optimal. E.g. you can solve most routing problems with >95% efficiency using heuristics with O(1) or O(log n) asymptotic time complexit
by faragon 11y ago
There is no need for the optimal. E.g. you can solve most routing problems with >95% efficiency using heuristics with O(1) or O(log n) asymptotic time complexity.
- devilsavocado 11y agoSure, but that is kind of beside the point. For most problems where the distinction between P and NP is important, the biggest being encryption, "95% efficiency" is absolutely useless.
- faragon 11y agoUntil a "95% efficiency" heuristic/approximation can be applied to a primality test, in that case (e.g. if someone finds a geometric heuristic for primality).