Solving vs. Verifying

When a friend asks me to check their math homework, I never think twice about it.

I scan line by line. I check whether each step follows from the one before it. I catch the mistake in question 3, hand it back, and we move on. The whole thing takes a few minutes. My friend spent close to an hour on those same problems.

The gap between those two experiences felt completely obvious to me the first time I thought about it. Of course checking is easier. You already have the answer in front of you. You are not searching for anything. You are just confirming that what is already there holds up.

What I did not realize at first is that this obvious, unremarkable gap is exactly what $\mathcal{P}$ vs $\mathcal{NP}$ is asking about. And that despite feeling completely obvious, nobody has been able to prove whether it is real or an illusion.

---

Two Different Jobs

Solving and verifying are not the same task done at different difficulty levels. They are fundamentally different jobs.

When you solve a problem, you start with nothing. The answer does not exist yet. You have to construct it. That means searching through a space of possibilities, trying paths, hitting dead ends, backtracking, trying again. The entire burden is on you. Nobody is helping. The answer could be anywhere.

When you verify a proposed solution, the answer is already there. Someone hands it to you. Your job is not to find anything. Your job is to walk along the path they drew and confirm it goes where they claimed. You are not navigating a maze. You are checking whether a single route through the maze is valid.

The solver has to find the route. The verifier just has to walk it.

These sound like a big difference. And they feel like a big difference. The question $\mathcal{P}$ vs $\mathcal{NP}$ is asking whether that difference is mathematically real, or whether there is always a shortcut that makes finding as easy as walking.

---

The Rubik's Cube Version

I want to use the Rubik's Cube here because it is the clearest version of this asymmetry I have ever seen.

Learning to solve the Rubik's Cube took me months. Not because I am slow, but because solving genuinely requires you to build up a mental model of the cube, memorize specific move sequences, recognize patterns in the current state, and execute the right algorithm at the right moment. Every scrambled cube is a new problem. You have to figure out which tools apply and in what order.

Checking a solved Rubik's Cube takes about two seconds. Six faces. Each face one solid color. Green: done. White: done. Red, blue, orange, yellow: done. That is it. The check is $O(1)$ in the number of faces, because there are always exactly six. It does not matter how the cube got solved or how many moves it took. The verification is instant.

The person who solved it and the person who checks it are not doing the same thing at different speeds. They are doing entirely different things. One of them is working. The other is looking.

---

What This Looks Like Across Problems

The same gap shows up in every problem we have talked about in this series.

🧩 Sudoku

Solving: You start with a partially filled grid. You try a number in one cell, follow the consequences through the grid, hit a contradiction somewhere, erase it, and try something else. For a generalized $n \times n$ Sudoku, the number of possible completions grows exponentially with $n$. Even expert solvers using elimination techniques are working against a fundamentally large search space.

Verifying: Someone hands you a completed grid. You scan each row: nine distinct numbers, no repeats. Each column: same check. Each $3 \times 3$ box: same check. For a standard grid, this is done in under a minute. For a generalized $n \times n$ grid, it runs in $O(n^2)$ time. Polynomial. Fast. Completely manageable regardless of how large the grid is.

🗺️ Traveling Salesman

Solving: You have $n$ cities. You need to find the shortest route that visits every one exactly once and returns home. The number of possible routes is $(n-1)!$. For $n = 20$ cities, that is over $10^{17}$ routes. Nobody checks them all. We use clever approximations, but no polynomial-time exact algorithm is known.

Verifying: Someone hands you a specific route and claims it has total distance less than $k$. You add up the distances along that route and check whether every city appears exactly once. This takes $O(n)$ time. You are just walking the route they gave you and adding numbers.

➕ Subset Sum

Solving: Given a set of integers, find a subset that adds up to exactly zero. The number of possible subsets is $2^n$. Post 6 showed what $2^n$ looks like for large $n$. At $n = 100$, you are looking at more subsets than there are atoms in the observable universe. No polynomial-time algorithm is known.

Verifying: Someone hands you a specific subset and claims it adds to zero. You add the numbers in that subset. This takes $O(n)$ time. Done.

📝 Math Homework

Solving: Blank page. You try an approach. Maybe it works, maybe it does not. You are constructing the answer from nothing, step by step, without knowing in advance whether the direction you picked will lead somewhere.

Verifying: Someone hands you their completed work. You read each line: does this follow from the one before it? Is the algebra correct? You are not navigating. You are confirming. The structure is already there. Your job is just to check whether it holds up.

---

The Formal Picture

Let's put what we now have into precise language, because the informal version is not enough to make the question rigorous.

Post 7 defined $\mathcal{P}$: the class of decision problems where a deterministic Turing machine can find the answer in polynomial time. These are the problems where solving is fast.

Post 8 defined $\mathcal{NP}$: the class of decision problems where, for every yes-instance, a short certificate exists that a deterministic Turing machine can verify in polynomial time. These are the problems where verifying is fast.

We also established in post 8 that $\mathcal{P} \subseteq \mathcal{NP}$. If you can solve a problem in polynomial time, you can certainly verify a proposed answer in polynomial time too. Just solve it yourself and compare. So everything in $\mathcal{P}$ is automatically in $\mathcal{NP}$.

The open question is whether the reverse is true:

$\mathcal{P} \stackrel{?}{=} \mathcal{NP}$

Does every problem with fast verification also have fast solving? Or are there problems sitting inside $\mathcal{NP}$, fast to verify, that are genuinely beyond the reach of any polynomial-time solving algorithm?

---

Why the Obvious Answer Is Not a Proof

This is the part that surprised me.

The asymmetry between solving and verifying feels so clear that it seems like the answer should be obvious: of course they are different. Of course $\mathcal{P} \neq \mathcal{NP}$. Doing the homework and checking the homework are not the same thing.

But I actually lean the other way. I think $\mathcal{P} = \mathcal{NP}$. I think the solution to every problem exists before we find it, and the gap we feel is not a permanent wall but a gap in our understanding. We just have not built the right mathematics yet.

Either way, feeling is not proof. And the gap between feeling and proof here is enormous.

To prove $\mathcal{P} \neq \mathcal{NP}$, you would need to show that no polynomial-time solving algorithm exists for some specific problem in $\mathcal{NP}$. Not just that we have not found one. That one cannot exist, not now, not ever, no matter how clever the approach.

That is a statement about every possible algorithm, including every algorithm that has not been invented yet. Ruling out an infinite space of possibilities requires a completely different kind of argument than just observing that checking homework is faster than doing it.

And to prove $\mathcal{P} = \mathcal{NP}$, you would need to exhibit one polynomial-time solving algorithm for one of these hard problems in $\mathcal{NP}$. A single example that works. That sounds easier, but nobody has found one in over fifty years.

The Feeling Is Not the Proof

Almost every researcher in the field believes $\mathcal{P} \neq \mathcal{NP}$. I personally believe $\mathcal{P} = \mathcal{NP}$. Neither position has a proof. The mathematical argument has not arrived in either direction, and the problem has resisted every known technique. We will cover exactly why in Phase 4.

---

What Happens If the Asymmetry Is an Illusion

It is worth sitting with the other possibility seriously, not just as a footnote.

If $\mathcal{P} = \mathcal{NP}$, it means the solving vs. verifying gap we feel is not fundamental. It means there exists a polynomial-time algorithm for Sudoku, for the Traveling Salesman Problem, for graph coloring, for hundreds of problems currently treated as intractable. We just have not found those algorithms yet.

Personally, I think this is the answer. I believe every problem has a solution. Not because I have a proof, but because I think that is how problems work: the solution exists first, already fixed, already out there, and the problem is just our failure to reach it yet. The algorithms for these hard problems exist. We have not built the mathematics to find them.

That is not a position most researchers hold. Most experts believe $\mathcal{P} \neq \mathcal{NP}$, that the asymmetry is real and permanent. And I understand why. The gap between solving and verifying feels enormous in every example we have looked at. But feeling is not proof in either direction. Nobody has proven $\mathcal{P} \neq \mathcal{NP}$ any more than anyone has proven $\mathcal{P} = \mathcal{NP}$. The question is genuinely open.

If I am right, it also means every encryption scheme protecting the internet collapses. RSA, the cryptographic system securing your bank account, relies entirely on the assumption that factoring large numbers is hard to solve even though it is easy to verify. If $\mathcal{P} = \mathcal{NP}$, factoring becomes easy. Everything built on top of that assumption breaks. That is a real consequence of the answer I personally lean toward, and I am not pretending otherwise.

Post 1 introduced these two worlds. Now that we have the formal machinery, the stakes are clearer. The solving vs. verifying gap is not just a mathematical curiosity. It is the assumption that modern digital security stands on.

Two Honest Positions

Most experts believe $\mathcal{P} \neq \mathcal{NP}$: the asymmetry is real, and some problems are permanently harder to solve than to check. I personally believe $\mathcal{P} = \mathcal{NP}$: the solutions exist, we just have not found them yet. Neither position has a proof. That is the whole point.

---

Where We Are

We have now built everything in Phase 1. We have algorithms, Turing machines, Big-O notation, the class $\mathcal{P}$, the class $\mathcal{NP}$, and now a careful look at the gap between solving and verifying that separates them.

The next post is the last in Phase 1. It brings everything together and states the core question properly, with all the vocabulary we have spent nine posts building. It also looks at what the question means for the world, and why despite being over fifty years old, it remains completely open.

See you there. 🚀

---

Azeon is an open documentation project by Aziz. If you find an error or want to suggest an improvement, open an issue on the GitHub repository linked in the sidebar.