Computational Complexity: Respect the P v NP Problem

Wednesday, June 10, 2026

Respect the P v NP Problem

There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as the more intuitive notion that everything efficiently verifiable is efficiently computable and the implications that has on our ability to compute.<br>I've written considerably about how artificial intelligence has affected the latter. In particular, how AI and other advances in computing have brought us to this Optiland of getting most of the good implications of P=NP while our cryptographic codes remain unbreakable.<br>But now with the recent advances in AI-created and assisted proofs, will AI change what we know about the formal mathematical statement? Is an AI-generated proof of P ≠ NP around the corner?<br>No, it isn't. I do not believe we will see a P v NP proof in my lifetime proven by man or machine, separately or working together.<br>While the disproof of the Erdős unit distance problem is an impressive AI achievement, keep in mind that for every AI math proof there are hundreds of problems that we have tried to solve with AI where we haven't seen progress. And there is a huge chasm between Erdős combinatorial conjectures and the Clay Millennium problems. AI will continue to improve, but there are limits.<br>People, particularly those outside of computational complexity, don't realize how difficult a mathematical challenge this is. Polynomial-time algorithms can work in strange and mysterious ways. They don't have to respect the semantics of an NP-search problem or do any searching at all. Bill gave me the following "algorithm" for clique: Take the eigenvalues of the adjacency matrix. For all we know, if there are two primes p and q such that the pth eigenvalue and the qth eigenvalue differ by more than 1/k then the graph has a k-clique. Of course this doesn't work. But to prove P ≠ NP, you need to prove not only that this algorithm doesn't work, but neither do any of the infinitely other potential algorithms for solving NP-complete problems.<br>We simply know of no way to manage general polynomial-time algorithms other than by simulating them. We know by relativization that simulation and diagonalization will not work to settle P v NP. Other attempts to understand polynomial time, like circuit complexity, proof complexity and algebraic geometry have gotten bogged down well below the full power of polynomial-time. At this time we don't even have a viable approach to settling the P v NP problem.<br>Don't waste your time trying a formal approach via Lean. (I'm looking at you Dmitry Khanukov) Computational complexity is very messy to formulate technically. I can't get an AI willing to give me a full Lean-verified proof of something trivial like P closed under complement, forget the PCP theorem. If someone or something does come up with a P ≠ NP, it'll be following the right intuitive approach, not a formalistic one.<br>At least start with something simpler, like showing BPP is in subexponential time, or SAT doesn't have quadratic algorithms. You won't succeed there either, even though these questions should be galactically simpler than P ≠ NP.

Posted by

Lance Fortnow

at

1:50 PM

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

12 comments:

Anonymous4:26 PM, June 10, 2026<br>The lack of "mathematical structure" in a lot of computational complexity + lack of copious amounts of results is a deadly combination for any (even heuristic) proof search techniques to get good. On the other hand, designing algorithm .... maybe?<br>ReplyDelete<br>Replies<br>Reply

David Monniaux4:29 PM, June 10, 2026<br>You commented that complexity theory is messy to formulate. If I were to formalize it, I'd go with the Bellantoni & Cook characterization of P. Do you know in what mess I'd be getting into?<br>ReplyDelete<br>Replies<br>Lance Fortnow4:59 PM, June 10, 2026<br>There are a lot of pieces there so it will be more tedious than you getting into trouble. Still, it will be tricky to even completely formulate P closed under complement.<br>Delete<br>Replies<br>Reply

Reply

Anonymous10:47 PM, June 10, 2026<br>my favorite way of formalizing P is through Circuit Value Problem, which is not too bad, and then defining the AC0 closure over it. Proving the closure under complement becomes also relatively easy.

The tricky part in formalizing is that often proving the equivalence of two different formulations is often non-trivial.

TM formulation, you can use the computation history as a strong, plus functions and predicates for working with strings. It is not too bad, for closure, given machine M, you can manipulate M to M' which would have the same valid computation history as the original, except the last state now not being the accepting state.

The main difficulty often is building the machinery required to do the intuitive manipulation of objects, that was also the technical part of Godel's theorem, but once you overcome...