3 ms·
My interpretation is: it's exponential in running time, although slightly faster than 2^n (exponent specifically is 0.86n). However, it uses polynomial space, w
by aklein 10y ago
My interpretation is: it's exponential in running time, although slightly faster than 2^n (exponent specifically is 0.86n). However, it uses polynomial space, which hadn't been done before. Prior approaches used an exponential-size lookup table. So there is no implication of P=NP.