I Challenged AI to Solve a Math Problem That Could Change Humanity. Here’s What Happened.

Four rounds of experiments, thousands of mathematical tests, and one surprisingly simple discovery about why some problems are so difficult to solve.

What would happen if you asked artificial intelligence to solve one of the most important unsolved mathematical problems in human history? Not explain it, summarize existing research, or suggest a few ideas, but actually attempt to develop a solution. It’s the sort of question that sounds slightly ridiculous at first, yet becomes increasingly interesting when you consider how capable modern AI systems have become.

I decided to find out. I challenged ChatGPT to tackle a mathematical problem with potentially enormous consequences for humanity, gave it considerable freedom to investigate, and encouraged it to question its own conclusions. Over four rounds, we developed algorithms, constructed mathematical arguments, tested thousands of examples, and repeatedly discovered flaws in approaches that initially appeared promising.

We didn’t solve the problem. But what happened along the way turned out to be considerably more interesting than watching an AI confidently produce a few complicated equations. In particular, we encountered a strange question that gets to the heart of mathematical problem-solving:

Why can AI solve a problem with hundreds of variables almost immediately, yet struggle to prove that a much smaller problem has no solution?

The answer involves mathematical logic, exponential growth, and a powerful idea: sometimes the difference between an impossible-looking problem and an easy one is recognizing what the problem actually represents.

Choosing a Million-Dollar Mathematical Problem

Before beginning the experiment, I needed to choose which problem to investigate. There are countless unsolved mathematical questions, but I wanted one whose solution could potentially benefit humanity in a practical and meaningful way. That led us to one of the seven Millennium Prize Problems established by the Clay Mathematics Institute: P versus NP.

Each Millennium Prize Problem carries a $1 million award for a qualifying solution, and P versus NP remains unsolved as of October 2026. Its significance goes far beyond the prize money. Depending on how the question is resolved, it could fundamentally change our understanding of what computers can accomplish efficiently.

The question itself is surprisingly straightforward:

If you can quickly check whether an answer is correct, can you also quickly find that answer?

Imagine someone hands you a completed Sudoku puzzle. Checking that every row, column, and square follows the rules is relatively straightforward. But if that same person hands you a blank puzzle, finding the correct arrangement can require considerably more work.

For an ordinary nine-by-nine Sudoku, modern computers have no trouble solving most examples. However, mathematicians study generalized versions of such problems that can grow indefinitely. As their size increases, the number of possibilities can become astronomical, even though checking a proposed completed solution remains relatively easy.

That’s the distinction behind P versus NP, although the technical definition is more precise. The letter P refers to decision problems that can be solved in polynomial time, while NP refers to decision problems for which a proposed yes-answer can be verified in polynomial time. We already know that P is contained within NP; the unresolved question is whether the two classes are actually equal.

Why Polynomial Time Matters

Suppose an algorithm requires approximately (n^2) operations to solve a problem containing (n) variables. If we double the number of variables, the amount of work increases by a factor of four. That’s not necessarily trivial, but it grows at a relatively manageable rate.

Now consider an algorithm requiring (2^n) operations. Adding just one variable doubles the amount of work, and adding ten multiplies it by 1,024. This is called exponential growth, and it’s one of the main reasons seemingly simple mathematical problems can become computationally overwhelming.

Number of variables	(n^2) operations	(2^n) operations
10	100	1,024
20	400	1,048,576
30	900	1,073,741,824
40	1,600	1,099,511,627,776

These are illustrative operation counts, not measurements of our algorithms. But the difference is remarkable. At 40 variables, the polynomial expression requires only 1,600 operations, while the exponential expression exceeds one trillion.

There is an important qualification: polynomial time does not automatically mean an algorithm is fast enough for practical use. An algorithm requiring (n^{100}) operations would still qualify mathematically, despite being useless for many realistic applications. Nevertheless, discovering a polynomial-time algorithm for every problem in NP would represent an extraordinary theoretical development.

Could Solving P Versus NP Actually Benefit Humanity?

Potentially, yes, although the consequences depend heavily on the nature of the solution.

Many important real-world tasks involve searching for arrangements that satisfy complicated requirements. These include scheduling hospital staff, optimizing delivery routes, allocating manufacturing resources, and designing systems where thousands of constraints must work together. Researchers already use sophisticated optimization methods for such problems, but some instances remain extremely challenging.

A practical breakthrough in solving NP-complete problems could give us dramatically better ways to approach these tasks. It might also influence mathematical proof discovery, scientific research, and certain aspects of artificial intelligence. On the other hand, an efficient general-purpose solution could threaten cryptographic systems that rely on particular problems being computationally difficult.

But proving P = NP would not automatically create a useful optimization tool, and proving P ≠ NP would not make existing computers faster. The former would establish the existence of polynomial-time algorithms for NP problems, while the latter would establish that such a universal guarantee is impossible.

With those distinctions understood, we had our challenge.

Round One: Can We Eliminate Unnecessary Searching?

Our first attempt focused on what appeared to be an obvious source of wasted computation: repeatedly exploring the same possibilities.

Imagine trying to solve a complicated maze. You reach an intersection, explore several passages, and eventually discover that some of them lead to exactly the same remaining section of the maze. If you recognize that duplication, you can avoid repeating work you’ve already completed.

We wondered whether a similar approach could help solve a class of mathematical problems known as Boolean satisfiability problems, or SAT.

SAT problems consist of variables that can take only two values: true or false. Each problem contains logical requirements, and the goal is to determine whether any combination of variable settings satisfies all of them simultaneously.

Consider a simple requirement:

[A\l or B\l or C]

The symbol (\lor) means OR. This statement requires at least one of the three variables to be true, although two or all three may also be true. A SAT problem might contain hundreds or thousands of similar requirements, some involving variables that must instead be false.

For our experiment, we focused on 3-SAT, a version where each requirement contains no more than three logical terms. This is an NP-complete problem, meaning that a polynomial-time algorithm capable of solving every 3-SAT instance would establish P = NP.

Our initial strategy was to assign variables progressively while keeping track of the requirements that remained unsatisfied. Whenever two different partial assignments produced identical remaining requirements, the algorithm would merge them instead of investigating both separately.

The reasoning was sound. If two paths genuinely leave the same remaining problem, keeping both provides no additional information about whether a solution exists. The difficulty was determining whether the number of distinct remaining problems could always be kept small.

The First Obstacle

We implemented the method in Python and compared its answers against a separate brute-force checker. Across 1,656 tested SAT instances, the two approaches agreed every time. This was encouraging evidence that the implementation was behaving correctly on those examples, but it told us very little about its worst-case efficiency.

So we constructed special mathematical problems designed to expose weaknesses in the algorithm. One family used XOR relationships, where variables must follow rules about whether an even or odd number of them are true. These relationships could be arranged so that many different partial assignments left mathematically distinct remaining problems.

The results were revealing. In one test with 20 variables, the algorithm retained 1,024 separate residual formulas at a particular stage. With 24 variables, that number increased to 4,096.

We could prove that this particular approach and variable ordering generated exponentially many distinct remaining states. Yet the underlying mathematical problems were actually easy to solve using a different technique.

This was our first major lesson: eliminating duplicated work is useful, but it doesn’t guarantee that the remaining work will be manageable.

We subsequently repaired the approach for a restricted family of XOR problems using Gaussian elimination, a familiar algebraic technique for solving systems of equations. The repair worked, but it didn’t extend into a general polynomial-time solution for arbitrary 3-SAT.

Our first proposed breakthrough had failed. More importantly, we understood why.

Round Two: Could Algebra Replace the Search Entirely?

For the second attempt, I wanted the AI to move beyond simply organizing a search more efficiently. What if we could replace the search with an algebraic calculation?

Instead of testing possible answers individually, perhaps a mathematical expression could somehow represent every possibility simultaneously. We could then evaluate that expression and determine whether at least one valid answer existed.

We investigated a way to represent a SAT problem as a polynomial whose mathematical properties reveal whether the problem has any satisfying assignments.

There was a particularly tempting shortcut. If every logical requirement could be expressed algebraically, perhaps we could multiply the corresponding expressions together and evaluate the result without ever examining each possible true-or-false assignment.

Unfortunately, even a very small example exposed a flaw.

Consider the contradictory requirements:

[x\land\neg x]

The symbol (\land) means AND, while (\neg x) means NOT (x). In ordinary language, we are demanding that (x) be both true and false. Obviously, no Boolean assignment can satisfy both conditions.

One natural algebraic representation is:

[P(x)=x(1-x)]

If (x=0), the result is zero. If (x=1), the result is also zero. So far, everything looks reasonable because Boolean variables can take only those two values.

But now suppose we evaluate the polynomial at (x=0.5):

[P(0.5)=0.5(1-0.5)=0.25]

The expression produces a nonzero result, even though the original logical problem has no solution.

The flaw is that the simple polynomial behaves differently outside the Boolean values zero and one. Although there are mathematically valid ways to repair this representation, the required algebraic calculations can themselves become expensive.

We developed a more careful formulation and investigated algorithms for evaluating it. The implementation passed 250 randomized comparisons against brute force, but that wasn’t enough to establish the efficiency we needed.

When a Simple-Looking Problem Becomes Enormous

One especially interesting test involved a SAT problem with only 14 variables. Every requirement shared a common variable, which meant that setting that one variable to true immediately satisfied the entire formula.

The problem was easy.

However, our explicit-table algebraic elimination method still constructed an intermediate table containing 16,384 possible assignments. It had turned a simple problem into a much larger calculation.

That was the opposite of what we wanted.

The underlying issue was becoming clearer. Mathematical expressions can be wonderfully compact, but expanding them into another representation can create enormous amounts of unnecessary work.

This wasn’t evidence that P ≠ NP. It was evidence that our particular mathematical representation was sometimes a poor choice.

The second attempt failed to resolve the problem, but it pointed us toward an increasingly important idea: perhaps an effective solver needs to understand the structure of a problem before deciding how to solve it.

Round Three: What If We Combine Several Mathematical Methods?

For Round Three, we changed our strategy again.

Rather than expecting one mathematical technique to solve everything, we built a hybrid solver that could use different methods depending on the problem. It incorporated logical simplification, XOR equations, Gaussian elimination, smaller independent components, and branching when simpler techniques were insufficient.

The idea was appealing because different kinds of mathematical problems have different strengths and weaknesses. A system of linear equations might be solved efficiently with algebra, while another type of logical system might be better handled using graph theory.

However, we discovered an important complication: combining two individually manageable types of constraints can recreate the full difficulty of a general SAT problem.

For example, problems consisting only of two-literal SAT clauses can be solved in polynomial time. Systems consisting only of XOR equations can also be solved in polynomial time. Yet suitably combining these two kinds of constraints produces a problem that is NP-complete.

We demonstrated this through an exact mathematical construction that transformed ordinary three-literal SAT rules into combinations of two-literal clauses and XOR equations. The transformation preserved whether a solution existed, showing that the interaction between the two supposedly easy systems could still represent arbitrary 3-SAT problems.

This result reflects established ideas in computational complexity rather than a new mathematical discovery. Nevertheless, it was a useful warning for our experiment.

Combining several efficient mathematical tools does not automatically produce an efficient algorithm for every problem.

The Experiment Starts Getting Interesting

The hybrid program passed 3,034 independently cross-checked SAT instances without any answer mismatches. It also handled structured problems containing hundreds of variables without needing to branch through possible assignments.

But we needed something harder than random test cases.

I wanted the AI to face a mathematical problem that was obviously impossible to a human but potentially troublesome for a search-based algorithm.

That’s when we introduced the pigeonhole principle.

The Pigeonhole Problem: A Surprisingly Difficult Way to Prove Something Obvious

Imagine that you have eight pigeons and seven empty holes. Every pigeon must occupy exactly one hole, and no hole can contain more than one pigeon.

Can you assign all eight pigeons successfully?

Of course not. There are more pigeons than holes, and the rules prohibit sharing. We don’t need to examine every possible arrangement to recognize the contradiction.

But suppose we translate this simple scenario into a SAT problem. We create Boolean variables representing whether a particular pigeon occupies a particular hole, along with logical requirements describing which assignments are allowed.

The resulting formula no longer explicitly says, “Eight pigeons cannot fit into seven holes.” It simply contains a collection of logical constraints.

Our Round Three solver had to investigate possible assignments and infer contradictions from those constraints.

The number of recursive solver calls began increasing rapidly.

Problem size	Recursive calls
4 pigeons, 3 holes	9
5 pigeons, 4 holes	37
6 pigeons, 5 holes	199
7 pigeons, 6 holes	1,218
8 pigeons, 7 holes	8,650

These were measurements from our research implementation, not general performance limits for SAT solvers. A recursive call can also contain substantial computational work, so the counts aren’t interchangeable with execution time.

Nevertheless, the pattern revealed a serious weakness. As the problem grew, the algorithm needed dramatically more recursive calls to establish something we could recognize immediately through simple counting.

Here was the question I found so fascinating:

Why could our solver handle certain problems with hundreds of variables, yet struggle to prove that eight pigeons couldn’t fit into seven holes?

It wasn’t because the smaller problem contained more variables or complicated arithmetic. It was because the solver was searching through possibilities instead of recognizing the mathematical structure responsible for the contradiction.

And that observation led directly to Round Four.

Round Four: Teaching the Algorithm to Recognize What It’s Looking At

For our fourth attempt, we tried something different.

Instead of giving the solver yet another way to search, we developed a specialized recognition system that could identify when certain SAT formulas represented assignment problems. Once it recognized the structure, it could translate the relevant constraints into a problem from graph theory.

Graph theory studies relationships between objects. In this case, we could represent pigeons on one side, holes on the other, and connections between them wherever a particular pigeon was permitted to occupy a particular hole.

This creates a bipartite graph, a network containing two groups of objects with connections running between the groups.

The goal then becomes finding a matching: a set of connections that assigns every pigeon to a different permitted hole.

Unlike general 3-SAT, bipartite matching can be solved in polynomial time. We implemented a matching-based recognizer that checks whether a formula belongs to a particular class of assignment problems and, when it does, uses a matching algorithm instead of ordinary SAT branching.

The difference was striking.

The Results That Surprised Me

The Round Four solver revisited the same pigeonhole problems that had troubled the previous version.

Problem	Round Three	Round Four
4 pigeons, 3 holes	9 calls	1 call
5 pigeons, 4 holes	37 calls	1 call
6 pigeons, 5 holes	199 calls	1 call
7 pigeons, 6 holes	1,218 calls	1 call
8 pigeons, 7 holes	8,650 calls	1 call
9 pigeons, 8 holes	More than 30,000 calls attempted	1 call

For the nine-pigeon example, the previous implementation reached a 30,000-call limit without finishing. The new version determined that the assignment was impossible within one top-level solver call.

We then increased the problem to 11 pigeons competing for 10 holes. When translated into SAT, this produced 110 Boolean variables and 561 clauses.

The new solver identified the assignment structure and determined that the problem was impossible in a single solver call. One recorded run completed in approximately three milliseconds, although that figure is specific to the experimental implementation and computer environment.

To be clear, one solver call does not mean one elementary mathematical operation. The call included the work needed to recognize the structure and run a matching algorithm. Still, the improvement over thousands of recursive searches was substantial.

We also tested the Round Four implementation against 1,405 small SAT instances whose answers could be checked using exhaustive enumeration. Every result agreed with the reference checker.

We hadn’t found a universal shortcut for SAT. We had found a way for this solver to recognize a special mathematical problem and stop treating it like an arbitrary collection of logical puzzles.

The Mathematics Behind the Improvement

The mathematical foundation for the new method is a result known as Hall’s Marriage Theorem, established by mathematician Philip Hall in 1935.

Despite its unusual name, the theorem has practical applications to matching and assignment problems. It describes when a collection of objects can each be matched with a distinct compatible object from another collection.

Imagine five employees who need five separate workstations. Not every employee necessarily has access to every workstation, so simply having the same number of people and stations doesn’t guarantee that an assignment is possible.

For instance, suppose three employees can only use two particular workstations. Even if ten other workstations are available elsewhere, those three employees cannot all be accommodated unless at least one has access to another station.

Hall’s theorem captures this condition mathematically:

[\boxed{|N(S)|\geq|S|}]

Here, (S) represents any chosen group of employees, while (N(S)) represents all workstations accessible to at least one employee in that group. The vertical bars mean “the number of elements in this set.”

The theorem says that a complete assignment exists exactly when every possible group of employees has access to at least as many distinct workstations as there are employees in that group.

If we can find even one group that violates this condition, the assignment is impossible.

For the 11-pigeon, 10-hole problem, the contradiction becomes:

[|N(S)|=10,\qquad |S|=11]

And therefore:

[\boxed{10<11}]

That’s it. We have a mathematical explanation of why no valid assignment exists, without needing to enumerate all possible arrangements.

A Proof That Can Be Checked Independently

An especially valuable improvement in Round Four was that the program could produce a certificate of impossibility.

Instead of simply reporting that the SAT formula had no solution, it identified a group of objects with too few available destinations. A separate verification program could then check that certificate without repeating the SAT search.

For the larger pigeonhole example, the certificate identified all 11 pigeons and their 10 available holes. We also generated certificates for 163 randomly constructed unsatisfiable matching problems, and the independent checker verified them successfully.

This matters because there is a substantial difference between an algorithm saying, “I couldn’t find a solution,” and producing a mathematical argument that demonstrates why no solution exists.

But we must be careful about what the result proves. Hall’s theorem is established mathematics, and researchers have long studied ways of exploiting matching structure in satisfiability problems. Our implementation applied those ideas successfully to a restricted class of formulas; it did not establish that every SAT problem can be converted into a matching problem efficiently.

Why Didn’t This Solve P Versus NP?

At this point, it might be tempting to imagine that we had found the missing ingredient.

If the solver could recognize assignment problems, why not teach it to recognize dozens of other mathematical structures? Some problems might become easier through graph theory, others through algebra, and others through logical simplification.

That’s a promising engineering strategy, but it doesn’t resolve the mathematical question.

The difficulty is that we still need to prove the algorithm can solve every possible 3-SAT instance in polynomial time. Recognizing several special classes, even very large and useful ones, is not enough if other instances remain outside those classes.

There’s another complication. As we established during Round Three, combining individually easy types of constraints can create an NP-complete problem. Even if we develop efficient specialists for each individual component, the interactions between those components can remain difficult.

We also have to account for the cost of recognizing a structure in the first place. An algorithm might solve a recognizable problem quickly but spend excessive time trying to determine whether an arbitrary input belongs to that category.

In other words, a truly general solution requires more than a collection of useful shortcuts. It requires a mathematical guarantee about all valid inputs, including adversarial cases deliberately constructed to defeat our favorite techniques.

Our experiments never established such a guarantee.

So What Did AI Actually Accomplish?

Across four rounds, we developed and tested several increasingly sophisticated approaches to Boolean satisfiability.

The first explored sharing repeated partial solutions. The second investigated algebraic representations and polynomial calculations. The third combined multiple established solving techniques, while the fourth added structural recognition and graph-based matching.

Each round gave us something useful to investigate, but each also revealed limitations that prevented us from claiming a general solution.

The most impressive practical result was the Round Four matching-based approach, which dramatically reduced recursive solver calls for a specific family of difficult-looking SAT encodings. We also generated independently checkable certificates demonstrating why certain assignment problems had no solutions.

However, none of these methods constitutes a new proof of P = NP or P ≠ NP. Much of the underlying mathematics was already known, and our code has not undergone an independent specialist audit or comprehensive academic novelty review. The experiments demonstrate how established mathematical ideas can be combined and tested, not that artificial intelligence has discovered a revolutionary new theorem.

That distinction is important because AI-generated mathematics can be persuasive even when it contains errors. Correct answers on thousands of test cases are useful evidence, but they cannot establish a statement about every possible mathematical input.

A rigorous proof must survive every case covered by its assumptions, not merely the cases we happened to test.

What This Experiment Taught Me About Artificial Intelligence

When I started, I imagined a dramatic possibility: perhaps AI could approach a famous mathematical problem without the same preconceptions as a human researcher and stumble upon something extraordinary.

That wasn’t what happened.

Instead, the experiment revealed how quickly apparently promising mathematical ideas can encounter subtle limitations. An algorithm might be logically correct but computationally inefficient. An elegant equation might describe a problem perfectly while being just as difficult to evaluate as the original problem was to solve.

I also found it interesting how differently the AI performed depending on how the problem was represented. It could handle a structured system containing hundreds of variables, yet an apparently simple counting contradiction could produce thousands of recursive calls when expressed in a less helpful form.

Of course, human mathematicians have understood the importance of choosing good representations for a very long time. What made this experiment engaging was watching that principle emerge repeatedly through our own attempts, mistakes, corrections, and tests.

And perhaps that’s where AI currently offers some of its most interesting potential for independent research: not necessarily by immediately solving famous open problems, but by helping people explore unfamiliar mathematical ideas, implement experiments, and investigate why particular approaches succeed or fail.

Used carelessly, it can generate confident nonsense. Used critically, with reproducible experiments and mathematical verification, it can become a useful research assistant.

Would I Try This Again?

Absolutely.

Four rounds barely scratch the surface of a problem that has challenged mathematicians and computer scientists for more than half a century. Although we investigated several distinct methods, we worked with a limited collection of mathematical techniques and experimental programs.

There are still countless avenues to explore, including better structural decomposition, mathematical proof systems, algebraic techniques, and algorithms that produce independently verifiable explanations for their answers.

I would be particularly interested in continuing to develop systems capable of identifying the underlying mathematical structure of problems automatically. Not because we’ve established that this will solve P versus NP, but because Round Four demonstrated how powerful that ability can be for the right class of problems.

There’s also something refreshingly honest about an experiment that doesn’t reach its intended destination. We tried something ambitious, found weaknesses in our ideas, and learned enough to ask better questions.

The question we began with was whether AI could solve an unsolved mathematical problem with potentially enormous consequences for humanity.

After four rounds, the answer is that we did not solve P versus NP.

But we did encounter an intriguing lesson about mathematics and computation: the apparent size of a problem doesn’t necessarily determine its difficulty, and understanding its structure can sometimes be vastly more valuable than searching through its possible answers.

And for an experiment that began with an admittedly outrageous challenge, I think that’s a result worth sharing.

---

Sources and Research Notes

The mathematical background in this article draws on the Clay Mathematics Institute’s official P versus NP description, introductory material on Hall’s Marriage Theorem, research on SAT backdoors and tractable problem classes, and established approaches used in SAT software such as CryptoMiniSat.

The experimental findings come from four rounds of Python implementations and recorded tests conducted with ChatGPT in October 2026. Correctness checks compared generated SAT instances with independent exhaustive-enumeration programs where computationally feasible. Performance figures describe the specific experimental implementations, not standardized benchmarks against state-of-the-art SAT solvers.

These experiments have not established a new mathematical theorem of general significance, and none of the results constitutes a solution to the P versus NP problem. The associated research packages contain the mathematical derivations, code, test records, and reproduction instructions for closer examination.