A Homological Proof of P != NP: Computational Topology via Categorical Framework

quamserena

The GitHub repo 404’s and likewise with the Docker image. Where's the code?

https://github.com/comphomology/pvsnp-formal

steego

The Github user doesn't even exist.

Who writes Lean code in the actual paper but doesn't create a repo or even a username?

emtel

The paper seems to make no mention of the natural proof barrier, so it is almost certainly not a proof of what it claims

soup10

what's the natural proof barrier

seanhunter

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

soup10

i see, thanks

rescrv

I'm not sure if this is real, but the abstract says machine-verified.

seanhunter

Yes. From a quick scan of the paper, it includes a formal proof in Lean4. That said, it is very long and complicated, with lots of steps in the chain (as you might expect) so it would need to be checked carefully to ensure it proves what it claims to prove.

Lean uses Curry-Howard correspondence, so how proofs work is you declare your propositions as types and then your proof is actually a recipe that goes from things that have already been established and finishes by instantiating that type. The guarantees there are very strong - if you succeed in instantiating the type you have definitely proved something. The question is whether you have proved the thing you said you have. So here scanning the proof (it’s like 100 pages and I am sick so definitely sub-par intellectually) they use category theory to embed the problem, so the proof is actually a proof of the properties of this embedding. So if there is a problem with the proof, my guess would be that it would lie in the embedding not being exactly representative of the problem somehow.

It seems a pretty serious attempt though- it’s not just some random crank paper.

rescrv

Thank you! This is the kind of comment I hoped to see.

I'm betting it was published in a hurry. I know I would hit "publish" within 24 hours of creating such a result, and would hope it would go wide. I'd publish to arxiv before getting clearance to release the code. I bet that's what happened here.

I appreciate your explanation of the Curry-Howard correspondance. I was familiar with it, but not with Lean in particular. I'd heard of Lean, but didn't know how it worked.

Thank you again!

krackers

For a claim this big, I'm surprised only one author. Not even an advisor?

rescrv

Once upon a time, people published solo often. It's just harder to do things like that these days.

gus_massa

In the last few months, I've seen a proof of P=/!=NP every two weeks in /newest, so color me skeptic.

beanshadow

[dead]

HN

A Homological Proof of P != NP: Computational Topology via Categorical Framework

A Homological Proof of P != NP: Computational Topology via Categorical Framework