4 ms·
If I'm not mistaken, showing P=NP doesn't necessarily guarantee that the solution is quick and likewise being able to quickly solve NP problems doesn't require
by lojack 11y ago
If I'm not mistaken, showing P=NP doesn't necessarily guarantee that the solution is quick and likewise being able to quickly solve NP problems doesn't require showing that P=NP.
- sacado2 11y agoDepends on how you define "quick". But, sure, finding an algorithm that solves SAT in O(1.0000001^n) (still exponential) would be much better in practice than finding one that would solve it in O(n^100) (although polynomial).