Polynomial-time algorithms with huge exponent/constant
Here are two screenshots from An Energy-Driven Approach to Linkage Unfolding by Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben,  James F. O’Brien, SOCG 2004: