Hacker News Reader

Another thing. It's known that a proof resolving P vs NP can't relativize, can't be "natural", and can't "algebrize". (See http://portal.acm.org/citation.cfm?id=1490272&dl=GUIDE&#... and its references for what this means.) The paper doesn't directly address how it avoids these barriers. It does mention the first two barriers in passing. Maybe the answer is obvious to anyone who could read this paper.

View on HN

In a cursory reading, I think I can address these criticisms. Although one would have liked the author to call out each in his introduction.

Naturalization: This proof is not combinatorial, it is based on a model of formal logic. This is addressed by the author directly.

Relativization: This is proof by contradiction and relies on understanding the solution space of k-SAT instances, not on diagonalization.

Algebrization: This proof looks beyond the size of small circuit into how the circuit inputs interact and how this interaction spreads throughout the circuit.

Reply on news.ycombinator.com