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.
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.
Also, I assume most people would not go through 3SAT to MAX2SAT, they would just reduce directly there.