AI vs Math vs P vs NP

Now that the robots have started attacking the Clay Mathematics millenium problems it's interesting when they'll get to P vs NP - you might ask, when they'll take this interest in mathematics right home to their own domain and start to seriously study their own limits by going back to the theory of computation.

There are great analogs between the progress in agentic computing and P vs NP. To briefly refresh your memory, P are problems we thing we can solve in polynomial time - i.e. as we pick larger and larger examples of the problem the time to solve them 'only' grows polynomially - and NP are problems that are much harder but where solutions are easy to check - where the verification of a solution can be done in polynomial time.

Agentic coding workflows are analogous in the sense, that the reason for the agentic explosion in software development is that verifying that programs do what we wanted them to do is a lot simpler than writing the programs. Agentic software development relies deeply on self-verification. It's the pivotal step - the agents will roll out solution after solution to the task they are given and then self-test proposed solutions and iterate based on the test results.

Formal mathematical proofs are themselves computer programs that find a path from statements known to be true to new statements we're interested in knowing the truth of. This is how the agentic coding workflow has transformed into succesful theorem proving - it's literally the same workflow; self test is possible - and if the robot is good enough at suggesting potential answers - verification and iteration does the rest of the work.

Back to P vs NP. Checking proofs is in P - verifying you only made legal steps in your program can be done quickly - but finding them obviously not - even satisfiability is NP complete. So if P was the same as NP we would have proven that all math is easy.

If - on the other hand - the robots start solving all the hard math problems and prove that P is indeed different from NP we have a weak paradox of sorts. The robots have proven that robots can't solve all the math problems... but they also solved one of the really hard math problems.

(Pseudo)-probabilistically of course - the robots are just efficient probabilistic searchers for solutions here - and indeed one of the comments I saw about OpenAIs Navier-Stokes solution was from someone in the fluid simulation field, noticing that - this was really not super interesting from an engineering point of view because Navier-Stokes fluid dynamics have been succesfully studied for decades in numerical mathematics with astounding succes. Similarly here we might the paradox is not strict in any way since P vs NP does not talk about equality or inequality with high probability. (There are separate classes and theorems in that space).

At any rate - it would be interesting to see the robots go to war on their own origin problems.

p.s. The cover image in this post is from this little satisfiability game I made. You can build your own expressions and see if they can be satisfied.