3 ms·
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?i
by bdr 16y ago
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&coll=GUIDE&CFID=99882395&CFTOKEN=52414657 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.
- brg 16y agoIn 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.