Case study: solving P-99 with LPTP and an LLM

Imagine a world where computers don't just follow rigid, robotic instructions but can actually understand the messy, fuzzy way humans describe problems. This is the frontier of Artificial Intelligence, specifically a branch called Large Language Models (LLMs). Think of an LLM as a super-smart, incredibly well-read student who has read almost everything on the internet. If you ask it to write a story, it can; if you ask it to write code, it can. But there's a catch: this student is prone to "hallucinations," meaning it might confidently invent facts or write code that looks perfect but secretly breaks when you try to run it.

To fix this, scientists use Formal Verification, which is like a super-strict math teacher who checks every single step of a student's homework to ensure it's logically impossible to be wrong. In the world of computer science, there's a famous set of challenges called the 99 Prolog Problems (or P-99). These are like the "gym workouts" for logic programming, a style of coding where you describe what you want to happen rather than how to make it happen step-by-step. The big question researchers are asking is: Can we let the AI student write the code based on a simple English description, and then have the math teacher instantly check if it's actually correct? This paper explores that exact experiment, blending the creative freedom of AI with the ironclad safety of formal logic.

---

The Experiment: A Coding Duo with a Strict Teacher

In this study, a team of researchers decided to test a new way of working called "vibe-coding" mixed with "vericoding." Imagine "vibe-coding" as asking a creative friend to build you a treehouse based on a rough sketch you drew on a napkin. You say, "I want a treehouse with a slide and a secret door," and they just start building. It's fast and fun, but the result might be wobbly. "Vericoding" is the opposite: it's like hiring an architect who demands blueprints, stress tests, and safety inspections before a single nail is hammered.

The researchers wanted to see if they could combine these two approaches. They used an AI model named Claude (specifically the Opus 4.6 version) to act as the creative builder. They gave it the first 33 problems from the famous P-99 list, which are written in simple, informal English. For example, one problem simply says: "Find the last element of a list."

The AI's job was to:

1. Write the Prolog code to solve the problem.
2. Write a test file to check if the code works on examples.
3. Write a formal proof to mathematically guarantee the code is safe, correct, and will always finish running.

To check the proofs, they used a tool called LPTP (Logic Program Theorem Prover). Think of LPTP as the strict math teacher who refuses to accept "it looks right" as an answer. It demands a step-by-step logical derivation for every claim.

The Results: A Mix of Magic and Math

The experiment was a success, but it wasn't a magic wand. The team managed to solve 33 out of 88 exercises (about 37.5%) using this method. Here is what happened behind the scenes:

• The Creative Part (Vibe-Coding): The AI was surprisingly good at the initial coding. It wrote 58 logic procedures (the actual code) and 508 test cases in just a few minutes per problem. It understood the English instructions and generated code that ran correctly.
• The Strict Part (Vericoding): This is where the real work began. The AI had to prove that its code was correct. It generated 257 lemmas (small mathematical facts) and wrote a staggering 11,800 lines of proof.
• The Human Touch: The researchers didn't just let the AI run wild. They manually checked every single file. They ran the tests, read the logical statements, and re-ran the proofs with LPTP. If the AI got stuck or wrote a proof that didn't make sense, the humans stepped in to give it a hint. For instance, for a problem about finding the last item in a list, the humans had to ask the AI, "Hey, how does this connect to the append function?" to help it formulate the right proof.

The Big Findings

The paper reveals a few key things about this new way of working:

1. AI is getting good at "Vibe-Coding": The AI could take a vague English description and turn it into working Prolog code very quickly. It even avoided "impure" tricks that real-world Prolog code often uses, sticking to a strict, logical style that the math teacher (LPTP) could understand.
2. AI needs a nudge for "Vericoding": While the AI could generate the code easily, proving why it was correct was harder. For complex functional properties (like proving the code does exactly what it's supposed to), the AI sometimes needed the human researchers to explain the logic in plain English first. Once the humans gave a hint, the AI could formalize it and prove it.
3. It's not a "Solved" Problem yet: The team didn't solve all 99 problems. Some took the AI only 15 minutes (like the simple "last element" problem), while others took several hours (like the "prime factorization" problem). The researchers note that for the hardest problems, the AI still struggles to come up with the right proof strategies on its own without human guidance.

A Glimpse into the Future: The "MCP" Connection

The paper also describes a new tool they are building called the Model Context Protocol (MCP). Currently, the AI and the math teacher (LPTP) talk through files and text documents, which is a bit like sending letters back and forth. The new MCP tool is like giving them a direct phone line. This allows the AI to ask the math teacher for help in real-time, check its own work instantly, and fix errors without waiting for a human to step in. They tested this with other AI models (like Gemini) and found that while some models could generate the ideas for proofs, only Claude was able to successfully generate the valid proofs that passed the strict checks.

The Bottom Line

This paper shows that we are entering an era where AI can act as a creative partner in writing complex, logical code, but it still needs a human "pilot" to steer it through the hardest parts. The AI can write the code and even draft the math proofs, but it sometimes gets lost in the details. By combining the AI's speed and creativity with a formal proof checker like LPTP, the researchers created a system that catches the AI's mistakes before they become real bugs. It's not a fully automated "fix-it-all" machine yet, but it's a powerful new tool that makes writing reliable software faster and safer than ever before.