Polynomial-time algorithms with huge exponent/constant
cstheory.stackexchange.com