Re:A Homological Proof of P != NP: Computational Topology vi...
by emtel on Wednesday October 22, 2025 @10:22PM
(#45677487)
The paper seems to make no mention of the natural proof barrier, so it is almost certainly not a proof of what it claims
[ Parent
| on HN ]
Re:A Homological Proof of P != NP: Computational Topology vi...
by soup10 on Wednesday October 22, 2025 @10:34PM
(#45677561)
what's the natural proof barrier
Re:A Homological Proof of P != NP: Computational Topology vi...
by seanhunter on Wednesday October 22, 2025 @10:45PM
(#45677640)
Natural proofs are a certain type of proof of the circuit complexity of boolean conditions. The barrier is that it has been proved that [1] natural proofs cannot be used for P vs NP.
I’m not sure that is a problem here given that as I understand it, natural proofs apply to circuit complexity approaches and they say the whole circuit complexity method has fundamental limitations which they describe thus:
The circuit complexity approach seeks to establish lower bounds by proving that NP problems require super-polynomial circuit sizes. While achieving success for restricted models such as monotone circuits, this approach has faced insurmountable barriers in establishing non-linear lower bounds for general circuits.
So they take an entirely different approach using category theory. It may have a similar limitation as the natural proof barrier (as far as I know), but as they dismiss the whole circuit idea and do something different I wouldn’t say them not mentioning the limitation of a specific type of circuit-based approach is that much of a problem.[1] assuming certain things which people generally believe to be true