[pclmulqdq]

I could believe that an O(n^5) algorithm, like what was presented here, can satisfy P==NP, but still maintain the status quo where P!=NP for all practical problems. That is honestly what matters most of the time.

Still, there's almost certainly a mistake in this paper.

[Vervious]

Though, P and NP are intrinsically defined asymptotically, so I'm not sure what it means for P != NP for all practical problems, other than saying that something like 80*n^5 is impractical to compute for n=10000, say.

[tgv]

How so? Impossibly large constants?

[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.

[jcranmer]

Not the person you're responding to, but that is one of the reasonable limitations of P=NP algorithm.

Many NP-hard problems tend not to be NP-hard on "average"; that is, reasonable heuristics can usually find you the correct answer. But there are certain structures that are (seemingly) difficult to solve. If you can exclude these structures by construction, the problem is in P; otherwise it's NP-hard. Boolean satisfiability is a good example here.

It also turns out from combinatorics that you can sometimes force necessary order on a structure by embedding it in larger space--sheer size imposes a structure of its own. Probably the most well-known example of this is the L=SL proof (admittedly, not generally well-known), where you can guarantee a walk that will visit all connected nodes of a graph without saving any history of nodes you've visited. Just replace every node with a new graph that is of size at least (IIRC) 3^65536. It's a constant factor, even if the constant is larger than the volume of the universe measured in Planck lengths.