[salty_biscuits]

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]

Only if the constant factor and polynomial exponent are small enough to be faster than exponential on real problem sizes.