3 ms·
Polynomial doesn't mean practical. In practice, O(n^100) is not an improvement over O(2^n). Also, we could imagine an algorithm that takes O(2^n) operation to
by GuB-42 7y ago
Polynomial doesn't mean practical. In practice, O(n^100) is not an improvement over O(2^n).
Also, we could imagine an algorithm that takes O(2^n) operation to verify and O(100^n) to find a solution. Both are exponential time (not NP), but the difference ensures that you can make it both safe and fast enough for use. I don't know if we could build such an algorithm if we had constructive P=NP though.
- bawolff 7y ago>Polynomial doesn't mean practical. In practice, O(n^100) is not an improvement over O(2^n). I literally said in my comment "and we have a constructive proof with an algorithm where the constants & degree aren't rediculous"