The Hard Limits of AI

I wanted to write this article because of a discussion I had with my friends recently about how, in my experience, although AI coding assistants can write SQL code very well, they tend to have a lot of trouble crafting SQL schemas, because relational logic is a very hard thing to do for both computers and humans. And then I read this excellent article by Ed Zitron about people trying to solve these hard problems with "Agentic AI Loops", that is, feeding LLM output into another LLM some number of times. So I want to explain why using Agentic Loops does not make hard problems easier to solve. In fact it is probably a bad idea to write large software applications with Agentic AI Loops, generally a very bad idea.

Before large language models were invented, "artificial intelligence" was less of a buzzword and more of a vast field of study covering an astonishing number of algorithms and software engineering techniques. The first book about artificial intelligence that I ever read was Ivan Bratko's Prolog Programming for Artificial Intelligence (free PDF download here). This textbook was first published in 1986, in that brief period of time in between the first and second AI winters, in which investors (especially the US military research program DARPA) became disappointed with the lackluster results of their investments into AI research. In the summer of 2026, the next impending AI winter hasn't happened yet, but it will any day now.

Nowadays, probably the most popular logic programming languages, or theorem provers, are the Lean and Rocq programming languages ("Rocq" was formerly known as "Coq", the name was changed to help English-speakers feel more comfortable talking about it). And of course several people are fine-tuning LLMs to make it easier for people to write better Lean or Rocq programs. Hopefully this will lead to us solving more of the mysteries of mathematics. But this story is not about logic programming, it is about the limits of logic programming.

Back in the 1980s, during a period when AI researchers were experiencing a surge in interest, people thought the Lisp programming language was itself a form of artificial intelligence. Languages like Prolog were also considered to be programming languages "for programming AI." Prolog was a little different in that it was not procedural (like Lisp) but declarative in style: you declared what goal you wanted the computer to solve, and the algorithm built-in to the interpreter of the language would solve the goal for you.

Prolog was 100% mechanical, as in, there was no deep learning, no artificial neural networks, no multi-layer perceptrons, or language transformers involved — no statistical AI methods used at all. It was just ordinary classical computation, like doing multiplication or long division with a pencil and paper. You follow the rules, you transform the input to an output, you get the answer. That is how Prolog does "AI."

solve:-
  m_disp(solve),              % solve submenu
  m_choose(solve,X),
  rdchar(stepmode,SM),
  (SM==`y , set_flag(stepmode,on)   % check for a y (scan code 21)
   ;
   set_flag(stepmode,off)),
  solve(X).                   % call solve w/ arity one with menu choice

solve(X):-
  init_solve(X),              % initialize all the stuff
  T1 is cputime,
  retractif(stage(_)),
  assert(stage(1)),           % the first stage will call the others
  stages,
  T is cputime - T1,
  state(S),
  cube_print(S),
  write($Done  time = $),
  write(T), nl, nl.
solve(X):-
  error('failing to solve'),
  halt.             % something wrong, back to main

stages:-
  repeat,
  retract(stage(N)),
  init_stage(N,Plan),        % Set the stage, get the plan
  state(S),
  cube_print(S),
  build_plan(Plan),
  improve(N,Plan),                % Put the pieces in the plan in place
  vw(N,V),                   % undo the stage view (done by init_stage)
  undo_view(V),
  N2 is N + 1,               % next stage
  assert(stage(N2)),
  N2 >= 7.

build_plan([]) :- !.
build_plan([H|T]) :-
  assert(impplan(H)),
  build_plan(T).

% init_stage goes to rubdata to get the table entries which define
% the heuristics for the stage

init_stage(N,Plan):-         % return list of target pieces for this stage
  wrfield(stage,N),
  cnd(N,Cands),              % set up candidate moves used by search
  build_cand(Cands),
  vw(N,V),                   % set up preferred view for stage
  set_view(V),
  pln(N,Plan),!.             % get list of target pieces

% improve - works through the list of target pieces for the stage.
%           it first checks to see if its already in place

improve(Stage,[]) :- !.
improve(Stage,[Piece|Rest]) :-
  impro(Stage,Piece),
  !, improve(Stage,Rest).

improve(Stage):-
  impplan(Piece),
  impro(Stage,Piece).

impro(Stage,Piece) :-
  add_criteria(Piece,Crit),                % Add new piece to criteria
  target_loc(Piece,Pos,Orient),            % Where is it
  impr(Orient,Stage,Pos,Piece),
  !.

In the above Prolog example code, you might be surprised what a small number of lines of code it takes to write a Rubik's Cube solver. It is a little long because it is not a naive solution that just tries everything, it actually plans and tries to improve on the plan, it performs common Rubik's-solving techniques, and detects and avoids dead-ends in the solution path. And the above program is fast, too. This is because Prolog interpreters are specially designed and optimized to solve logic problems like this.

The solving logic can all be defined in just 66 lines of code (with many more lines needed for other stuff), because in Prolog, the recursive loops and backtracking logic are almost entirely implied in the grammar of the language. So there is no need to explicitly write loops or conditional "if" statements, the loops and conditionals are all there "in between the lines." This is of course very useful when the vast majority of the work your algorithm does is looping over lots of states, testing each state, and backtracking when you hit a dead-end in the path toward the solution. And once you get used to the grammar, it can also be easier to read and understand this code because there is less code to read.

So are these techniques all obsolete now? Does modern LLM-based AI solve these problems better or faster? No, of course not, and the rest of this article is to explain why not.

In fact, for problems like playing Chess, or solving a Rubik's cube, a LLM-based AI is considerably worse at solving the problem than old-fashioned symbolic logic programs. And you may be tempted to ask, "couldn't we just tell Claude Code or some AI coding assistant to write the Prolog code for us now?" The answer to that is: sometimes, not always, and usually not without a lot of human intervention.

The thing about classical computation is that some problems are hard to solve. I mean, really, really hard to solve. Computer mathematicians have come up with kind of genealogy for classifying the difficulty of algorithms. These classifications are called complexity classes. And even though modern AI, like Large Language Models (LLMs) are statistical, not classical algorithms, they are computationally no more powerful than any traditional programming language like Prolog or Lisp. And so LLMs and modern AI are still subject to the same cold, hard mathematical constraints that the old AI systems of the 1980s were.

A brief introduction to complexity classes

(You can skip this part if you already know what an "NP-Complete" problem is.)

To categorize an algorithm into one of the many complexity classes, forget about the details of the input and output, instead focus on trying answer a simpler question: about how many steps does it take to compute the correct answer? If you have two numbers that are 20 digits long, can you guess how many steps it might take to add those two numbers? Can you guess how many steps it might take to multiply them?

If you learned how to add, subtract, multiply, and divide with a pencil and paper, you already have an intuition based on experience that some calculations are harder than others: it is easier to add and subtract than it is multiply or divide. Adding two 20-digit numbers will take about 20 steps. But multiplying two 20-digit numbers will take about 20 × 20 = 400 steps. Our number 20 here could be any number, let's call it "N." Addition will take N steps, multiplication will take N×N steps, that is to say N² number of steps.

This is how mathematicians classify algorithms. We call it Big-O notation. "O(N)" is a shorthand meaning an algorithm that take N steps. "O(N²)" means a program that take N×N steps. There are a variety of other classifications, for example:

• "O(log N)" means the base-2 logarithm of N number of steps (log₂20 equals a number between 4 and 5)

• There is also "O(1)", meaning you get the answer in basically one step regardless of how big the input is. So the computer program:

  1. Ignore the input.
  2. The answer is always zero.

  ...is an example of an "O(1)" complexity algorithm.

If you are very lucky, sometimes the problem you want to solve may seem to be an O(N²) turns out to be solvable in only O(log N) number of steps through a bit of clever re-arranging of the steps to eliminate duplicate work. Even if you don't manage to reduce the number of steps, when doing practical problem solving, you can still make some steps go faster: move things you use often closer together, or keep a note with the answer to a problem you see often so you don't otherwise have to calculate (this is called a "lookup table optimization"). But some problems simply have no shortcuts.

Once mathematicians started thinking about ways of classifying algorithms by difficulty, they started coming up with problems that were carefully constructed to be really hard to solve. And as it turns out, there are also completely unsolvable problems as well.

The "halting problem," for example, is easy to say but impossible to solve: can you write a program that checks if another program will loop forever? Looping forever is usually a bad thing, it tends to freeze-up your computer, so it would be nice to catch those programs before you try run them on your computer. How would we write a such a program?

Some programs can be checked, and you can easily see that it will loop forever.

1. Do nothing.
2. Start again from step 1.

...is a program that obviously loops forever. But as any computer hacker can tell you, it is easy to write hidden infinite loops into a program, in all sorts of ways. And as we found out early on (as far back as the 1940s), you will only ever be able to catch the easy-to-find loops, because being able to catch all possible looping programs is, in fact, mathematically impossible.

And of course, there are all kinds of other problems out there that are not impossible, but just very hard to solve. This is the class of NP-Complete problems:

• Finding the prime factors of a large number is so reliably difficult we actually based computer security on it for a while.

• Protein folding, that is, trying to figure out the 3D shape of a protein by analyzing it's sequence of component molecules, is another famously difficult problem in the NP-Complete class.

• "Program synthesis", or "program generation," that is to say writing code, is also in the NP-Complete class of problems, for the majority of all possible computer programs.

You guessed it: AI coding assistants write code, which makes them programs that were invented to solve an NP-Complete problem.

Modern AI still can't solve the unsolvable

It seems pretty amazing that an AI computer program can solve coding challenges and write computer programs and software. But an AI system is still just a computer program, no matter how you try to build it, no matter how big it gets or how much memory it takes or how many datacenters it takes to run the program, it is still just a computer program. So AI is still limited by the same complexity constraints that any other computer programs are. Regardless of whether you use an AI coding assistant or a Lean theorem prover to solve a coding challenge, the act of solving coding challenges is still a form of "program synthesis", and program synthesis is an NP-Complete problem.

I just want to be clear here: there are two different kinds of problem I am talking about.

1. The first kind is the problem of writing code. I will call this the "coding challenge," where you write a computer program. Solving this problem (this "challenge") is the NP-Complete problem, though technically it could be more complex than NP-Complete, for example, if you are unknowingly trying write a program to solve the impossible-to-solve halting problem.

2. The second kind of problem is the math or logic problem that the computer program solves when you run it, like adding two numbers. This problem can be in any class, from the very simple "O(1)" class to the impossible halting problem.

One question that I asked myself soon after I learned about the Prolog language was, "can I write a math equation that writes a program?" Or said another way, "can you write a logical formula that describes an entire computer program and have the computer write the program for you according to the formula?" Formal methods is the field of computer mathematics devoted to the study of that question. Unfortunately, writing formulas that describe to a computer how to write a program turns out to be even harder than just writing the program yourself, so in practice this is only ever done when it is extremely important that the written computer program be absolutely correct.

One of the more useful things about modern LLMs is that they do seem to be able to solve hard problems. The protein folding problem I mentioned earlier is one example of a problem that has been made much easier to solve with modern AI, such as with Google's AlphaFold technology.

LLMs do have some practical uses

How does AI help make a NP-Complete problem easier? It cannot reduce the number of steps it takes to solve. But in the real world (not the world of mathematics), we care about questions like "can we perform more steps at the same time to solve the problem in less time?" Here we say "less wall-clock time," to differentiate "time" in the sense of how long you have to wait, as opposed to "time" in the sense of how many steps it takes to solve a problem.

So one thing we can do to reduce the wall-clock time that it takes to compute all of those steps is to keep a record of all the answers to the most common problems. That way, if we ever encounter the same problem again, we can just lookup the answer, rather than duplicate the work of solving it again.

This is analogous to how we make arithmetic easier for ourselves, we basically use a lookup table. You probably don't need to count on your fingers anymore in order to solve the problem "3 + 5", you have the answer memorized. A computer can take similar shortcuts of memorization. Rather than actually count (or compute) things, they can keep a list of answers to common questions. If the list is small enough to search quickly with a search algorithm, and contains a large enough corpus of commonly asked questions, then the search algorithm will likely find the answer to the problem in less wall-clock time than it would take to compute the answer.

A LLM is built by essentially compressing a very large volume of textual information into a data structure that can quickly re-generate that information from lookup strings (what people call "prompts"). An AI coding assistant uses a LLM that contains the answers to many millions of coding challenges that software engineers tend to encounter often. The LLM can serve the same function as a very large and complex lookup table, where the "inference" algorithm is the lookup algorithm. And because we have very large datacenters available to us on the Internet, the inference that generates the code is often times faster than trying to write the code by yourself (though you may sacrifice code accuracy).

But solving a coding challenge is still a really, really hard, NP-complete problem, even with "lookup tables", by which I mean the LLMs, to help speed things up. It could take less wall-clock time to solve the well-known coding challenges, but the LLM won't be able to encode answers to all of the infinite number of coding challenges that exist.

Sometimes LLMs are even worse than Prolog or Lisp

So solving coding challenges is a very hard problem, in the NP-Complete complexity class. But you reduce the wall-clock time it takes to compute the solution with a highly technologically advanced lookup table such as a Large Language Model (LLM). And since most computer programs are composed of smaller, simpler programs working together, and a lot of those small, simple programs have well-known solutions, an AI coding assistant can absolutely help you write software faster.

However, even if you break-down your software into many smaller, common coding challenges for which there are already well-known answers, your software may yet contain coding challenges for which the answer is unknown to the LLM. Once the AI coding assistant has solved the all of the common coding challenges, what you are left with is still an NP-Complete problem to solve.

That may be the reason why LLMs appear to be really smart, and then suddenly appear to be really stupid. The "smart" things it does is really just knocking-out all of the smaller coding challenges that comprise your software application, copying and pasting solutions to these coding challenges that were already invented by smart humans. But as soon as it runs into a coding problem that is unknown to the LLM, the AI coding assistant just generates random output, what people call "lies" or "hallucinations." And random output is very unlikely to actually solve your coding challenge.

Agentic AI Loops are worse than you think

It gets worse. It is possible to fully simulate a complete computer system in a LLM datacenter (because the GPUs that run LLMs are Turing Complete), which means LLMs can simulate a classical computing algorithm like a Prolog program. But these simulations are tremendously inefficient. What may be solvable by a Prolog or Lisp program in a matter of milliseconds may take many minutes for an "agentic AI loop" to generate, if ever. This is because LLM inference is a basically a very complicated statistical search algorithm, and they are not optimized for symbolic computing the way Prolog or Lisp is.

So this is why, for example, a Chess program written in the 1970s running on an 8-bit computer with 4 kilobytes of memory can still beat a LLM at a game of Chess in the year 2026. And emulating a classical computer system in a LLM datacenter (in a GPU), while possible, is extremely slow and energy intensive. See my gallery of logic gate circuit simulators to see examples of emulating classical computing systems in a GPU.

And now our society at large finds itself in this horrible situation were people believe they can solve NP-Complete problems with agentic AI loops, and end up burning up billions of tokens in a few hours, not to mention how much energy and water this wastes in the datacenters that run these agentic AI loops.

I'll say it again: you can break your program down into smaller coding challenges, but once the the most common coding challenges have been solved by looking up the already known answers, what remains are the coding challenges for which writing the code is an NP-Complete problem. And LLMs not being optimized for this, makes a modern AI coding assistant worse at finding a solution than the old-fashioned AI of the 1970s and 1980s.

Can we teach LLMs to write Lean or Rocq code?

If you are wondering, couldn't we just teach AI coding assistant to write a Prolog, Lean, or Rocq program? Yes, of course we can, it has been done before. But these coding assistants will still only be able to quickly and easily solve the coding challenges that have already been solved by humans and used to "train" the LLM. Those other coding challenges will take a lot of effort to solve, and will probably not be best solved by a LLM.

As I said earlier, formal methods is the field of computer science that studies how we can check the correctness of programs, or to generate programs that are perfectly correct according to a logical formula. But this is so much more difficult to do than writing an ordinary computer program that it is usually not practical. So writing code from a logical proof of the program's existence is, in practice, only done when it is absolutely necessary that the cost of guaranteeing the correctness of the software is justified.

Another problem with teaching an AI coding assistant to use a theorem prover is that it is difficult to teach a LLM to recognize when it does not know the answer to a coding challenge. How do you teach it to recognize when it can't find the answer to a coding challenge, and when that happens, that it should write a Lean or Prolog program to solve the challenge instead? LLMs are defined to solve known problems. A LLM treats unknown problems as noise, as garbage. And when you feed it garbage in, you get garbage out, random output, hallucinations.

So how do you design an LLM to defer to a Lean or Rocq theorem prover instead of generating random output? It seems that no one yet knows.

It is not completely futile

To be perfectly fair, probably the vast majority of coding challenges that you will ever encounter in your life already have solutions to them written into the memory of the LLMs we use for AI coding assistants. It is in fact likely that the software that you personally want to write can be broken down into simpler coding challenges that can all be easily solved. It is probably not very often that an ordinary person writing software with an AI coding assistant will encounter a truly new and unknown coding challenge.

That said, there are times when you can easily take a program that solves an easy problem, and by changing one small, seemingly simple little thing about it, suddenly the problem to be solved becomes among the hardest NP-Complete problems to solve. For example, you might be asked to write a feature of an app that searches for a sentence a book. This is a substring search algorithm with complexity "O(N×M)" (M is the number of words in the sentence, N is the number of words in a book). You release the feature and the clients seem to be satisfied.

Then they come back asking for a "small" change: find sentences that are similar as well. So if you type "I said let's go" in the search bar, that should also be able to find "Let's go, I said." Suddenly, your app needs to solve the "Subgraph Isomorphism Problem," which is NP-Complete, and much more complex than O(N×M). You can cheat a little, using modern machine learning techniques, but this is an approximation and not guaranteed to give you 100% of the correct answers. If your clients can deal with a few misses, or a few nonsense matches, then it might be OK to use the statistical machine learning techniques. But if they really need precision, 100% of all matches, then they might have to buy a lot more computers to power their sentence search feature.

An AI coding assistant can write these algorithms because they are already known and well understood. It may even warn you that the algorithm you asked it to write will consume a tone of compute resources. But remember that these NP-Complete problems can blind-side you, especially if you are writing a larger piece of software. You may have broken down your software into a bunch of simple coding challenges, most of which are well-known, solved problems.

But then there may be that one last coding challenge unique to your situation that you need to solve to get your app to work, where trying to write the code for it correctly according to your specification turns out to be an NP-Complete problem not known to the AI coding assistant. If you run an agentic AI loop on that, you'll be spending a lot of money on tokens. So keep in mind, sometimes if you run into a difficult problem, one where the AI coding assistant keeps going back and forth between various wrong answers, spinning up lots of agents or lots of loops is not necessarily going to solve these problems, you may have come across one of those genuinely, mathematically difficult coding challenges.

It is very frustrating for me whenever I hear wealthy Silicon Valley venture capitalists or tech company CEOs speaking to tech journalists, or any of the AI-peddling influencers, about how LLMs will be able to solve any problem in the near future, as if somehow using LLMs could reduce the number of steps it takes to solve an NP-Complete problem. And it is frustrating to hear about so many people who do not even having a surface-level understanding of complexity theory waste so much energy running these agentic AI loops to write software. If you leave these machines to their own devices, a somewhat likely outcome is that these AI agents could end up emulating a Lean or Rocq interpreter in your GPU, which would be the worst, slowest, most expensive way to solve the problem of writing code. A more likely outcome will be random code that does not functions correctly at all. Because when a LLM doesn't know the answer, it just generates random output ("hallucinates").

So seriously, we all need to just chill out and wasting money on these agentic AI loops to generate slop code. The invention of the LLM did not settle the question of whether or not all NP class problems are in the set of P class problems.

By all means, keep using your AI coding assistants to help you write software, if it makes you more productive. But you still need to provide a lot of guidance to the AI assistant to ensure the code that was written was correct. Don't let it get into a loop trying to solve an NP-Complete coding challenge. And please, at least attempt to make it a little more efficient before you have other people start using it.

Appendix G.I.G.O. = Garbage In, Garbage Out

Can you teach a LLM or AI coding assistant to recognize when it has seen a problem for which it does not know the answer? Can we teach LLMs to recognize when an input coding problem does not yet have a pre-recorded solution, and that the coding challenge could be better solved by using a logic programming language such as Prolog, Rocq, or Lean?

Unfortunately no, that is not how LLMs work. Trying to use a LLM in combination with a traditional symbolic logic programming language to solve a coding challenge is, in an of itself, quite a challenge. An AI coding assistant will necessarily have a hard time recognizing the circumstances of when it should try to lookup the solution to the problem in it's memory, and when it should instead try to write a logic program to solve a coding challenge.

For the sake of demonstration, I wrote an Emacs program to scramble the words in this article just a little. So the scrambled text is not completely random. Statistically speaking, it still resembles English text, but with bad grammar. Then I fed this scrambled English into an ordinary commercial LLM chatbot (Google Gemini).

I didn't want to clutter this article with LLM-generated text, so I put the "conversation" in a separate page (click here). Please, observe the results, then tell me if you still think a LLM can be trained to identify when it's prompt contains an as-yet unrecognized coding challenge. If you feed an input with a statistically low probability of matching a memorized output, the LLM will not just give up it's search for an answer and try to generate a Lean or Prolog program to solve the problem instead, it always generates a statistically likely reply to an input even when the input itself is statistically unlikely.