Which is exactly why you want a Lean proof in the first place!
NL proofs rely on not-entirely-correct prior art, and contain countless holes both big and small. When formalizing human NL proofs it is probably very normal that the Lean proofs doesn't quite follow the NL proof.
Yes people have to service the use case of a single person. All sorts of models exist that are designed to be ran at home. Yes, you need a relatively beefy graphics card for it but if your machine can handle the latest video games at good graphics it can handle these local models. How well they compare against these things remains to be seen but apparently OpenAI released gpt-oss-20b which is comparable to o3-mini apparently in terms of reasoning power. There's also oss-120b which does require at least a company server to run but this should well be within the budget of a university.
The paper does not resolve P versus NP, but it does make an important advance in a closely related area. To prove that P ≠ NP, it would be enough to show that every algorithm for an NP-complete problem requires superpolynomial time. We cannot prove anything remotely that strong. For explicit NP-complete problems in unrestricted computational models, we cannot even prove superlinear lower bounds. There is therefore an enormous gap between the lower bounds we can prove and the superpolynomial bounds we would need.
VP and VNP are closely related algebraic analogues of P and NP. Here the paper proves new lower bounds for computing the permanent, a VNP-complete polynomial, in particular models of arithmetic computation: roughly (n^2\log\log n) arithmetic gates for unrestricted division-free circuits, and (n^4/\log n) size for the more restrictive formula model. These are still polynomial bounds, so they do not separate VP from VNP. But lower bounds on the resources needed to compute explicit functions are exactly what would ultimately be required for such a separation, and meaningful lower bounds of this kind are exceptionally rare.
NL proofs rely on not-entirely-correct prior art, and contain countless holes both big and small. When formalizing human NL proofs it is probably very normal that the Lean proofs doesn't quite follow the NL proof.
reply