[pclmulqdq]

When reducing one problem to another, you are allowed to have polynomial expansion in the problem size. If you are trying to take a practical problem and reducing it to MAX-2-SAT, you may have an n^2 or n^3 expansion. If you get lucky, the expansion may merely be a factor, like 2n or 5n. So now you're solving a problem that's at least O([big constant]*n^5), but could likely be O(n^10) or worse for any real problems.

Also, this algorithm is not easily parallelizable, so even O(n^5) can be an issue for n > 1000.

Also note that in this particular problem, n is a count of bits and logical ORs of pairs of bits, so getting to n > 1000 is a lot easier than you may think.

[tgv]

At n > 1000, exponential seems more of a problem. But 3SAT can apparently be reduced to MAX2SAT increasing the length by a factor 10, so that doesn't seem prohibitive to me.

[pclmulqdq]

I mean, the practical impact of this seems to be that the lower limit of where you can use a SAT solver or an LP solver to solve your problems increases by about a factor of 10 (or 100 at most). That's very useful, but still pretty small, and generally too small to really be useful on the hard problems that P = NP was "supposed" to crack. If this algorithm were able to be parallelized, that would be a different story.

Also, I assume most people would not go through 3SAT to MAX2SAT, they would just reduce directly there.