4 ms·
Depends, if it was a constructive proof by example for a useful problem (e.g. somebody finds a provable polynomial algorithm for the traveling salesman problem)
by salty_biscuits 7y ago
Depends, if it was a constructive proof by example for a useful problem (e.g. somebody finds a provable polynomial algorithm for the traveling salesman problem). Even without the polynomial reduction to other problems that would be pretty great...
- lonelappde 7y agoOnly if the constant factor and polynomial exponent are small enough to be faster than exponential on real problem sizes.