[cdavidcash]

"only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of".

And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.

[joe_the_user]

I'd tend to agree...

Taking a methods from a different domain in no way shows that the mechanics of those method don't reduce to the same mechanics as a "natural proof". Further, it makes the actual process much more obscure.

Indeed, statistics in general seems like a hard approach for overcoming the Razborov-Rudich limit, since the limit is on showing that a "typical" function has certain properties and anything statical seems like it would be "typical".

But who knows really, maybe Razborov-Rudich isn't correct, since in fully generality it relies on things that "mathematicians generally believe" (the existence of certain pseudo-random functions) rather than things that are definitely proven - as far as I know.

[long]

Again, I'm no expert, but relativization and algebrization are properties of proofs that invoke oracles, which this paper doesn't appear to do.

[cdavidcash]

Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there <i>does</i> exist an oracle A such that P^A = NP^A!

Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.

[long]

Ah, thanks for explaining!