| ▲ | vote_farisa_202 8 hours ago | |
The algorithm's runtime is in faster growing than O(exp(n^a)) for any a < 1. It's not subexponential in the sense that factoring is, which I believe has a secondary exponent of 1/3 under the best algorithms. It's still a big result, but it's mostly theoretical. It might help explain, structurally, why most SAT instances are far easier than an exponential model would indicate. | ||