The Core Question: Does $\mathcal{P} = \mathcal{NP}$?

I remember the day after that classroom discussion at FC College. The one where someone brought up P vs NP and I went home not being able to stop thinking about it. I opened a tab. Then another. Then five more. I kept running into the same sentence, written slightly differently each time: if a solution can be verified quickly, can it also be found quickly?

And I kept reading it, nodding, and not really getting it.

Not because the words were unclear. Because I did not have the ground under me yet. I did not know what "quickly" meant in a precise sense. I did not know what a complexity class was. I did not know why the question was even hard to answer.

That is what the last nine posts were about. Building the ground.

Now I am standing on it. And the view from here is genuinely exciting.

---

Everything We Built

Let me trace the chain, because it is worth seeing whole before we ask the question.

Post 2 gave us algorithms: finite, unambiguous, general instructions that produce correct output. They exist independently of whether anyone is consciously running them.

Post 3 gave us Turing machines: a precise universal model of what computation means. When we say an algorithm exists, we mean a Turing machine exists.

Post 4 gave us the two versions of that machine. Deterministic: one fixed path at every step. Nondeterministic: explores all paths at once, or equivalently, always guesses correctly. The $\mathcal{N}$ in $\mathcal{NP}$ comes directly from that second machine.

Posts 5 and 6 gave us Big-O notation and the reality of exponential growth. Polynomial time is the territory computers can reach. Exponential time is the territory that swallows the universe.

Post 7 gave us $\mathcal{P}$: problems solvable in polynomial time. Sorting, binary search, shortest paths, primality testing. If a problem is in $\mathcal{P}$, a computer can find the answer fast.

Post 8 gave us $\mathcal{NP}$: problems where yes instances have short certificates verifiable in polynomial time. Sudoku, TSP, graph coloring. If a problem is in $\mathcal{NP}$, a computer can check an answer fast.

Post 9 put those two experiences side by side and showed that checking genuinely seems easier than finding. Handing someone a completed Sudoku grid takes two seconds to verify. Constructing that grid from scratch is a completely different kind of difficulty.

All of that was setup. This is the question.

---

The Question, Stated Precisely

We know with certainty that:

$\mathcal{P} \subseteq \mathcal{NP}$

This is proven. If you can solve a problem in polynomial time, you can certainly verify a solution in polynomial time too. Just solve it again. The solving box sits inside the verifying box.

What nobody knows is whether those two boxes are actually the same box:

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

Is there anything in $\mathcal{NP}$ that is not in $\mathcal{P}$? Are there problems whose solutions can be verified quickly but can never be solved quickly, no matter what algorithm you try?

Or is the gap between checking and finding an illusion? Is there always, hiding somewhere, a polynomial-time algorithm for finding the answer, and we have just been too limited to see it?

---

Two Possible Worlds

If P ≠ NP

This is what almost everyone believes. The containment is proper:

$\mathcal{P} \subsetneq \mathcal{NP}$

$\mathcal{P}$ is a strictly smaller set than $\mathcal{NP}$. There are problems in $\mathcal{NP}$ that genuinely cannot be solved in polynomial time. Not because we have not found the right algorithm yet. Because no such algorithm exists. The gap between checking and solving is real, mathematically fundamental, and permanent.

This world is the one we already live in, whether or not it has been proven. Our cryptographic systems assume it. RSA encryption works because factoring large numbers appears to be hard. Every time you pay for something online, that transaction is protected by the assumption that $\mathcal{P} \neq \mathcal{NP}$.

If this is the answer, computers have hard limits that no engineering advancement will ever overcome. Some problems are simply out of reach. That is not a failure of cleverness. It is a fact about the structure of computation itself.

If P = NP

This is the world almost no one believes, but the one no one can rule out.

If $\mathcal{P} = \mathcal{NP}$, solving and verifying are equally hard. Every problem whose solution can be checked quickly can also be found quickly. The two boxes are the same box.

Every NP-Complete problem would have a polynomial-time solution. Not approximately. Exactly. Drug discovery would transform overnight. Supply chain optimization, circuit design, protein folding, scheduling: all of them would become tractable. AI systems that currently approximate answers would find optimal ones.

And then the other side: every encryption scheme protecting passwords, bank accounts, private messages, government systems would become breakable in polynomial time. The mathematical guarantee behind internet security would dissolve. The proof itself would probably arrive hand-in-hand with an algorithm: a construction that, once you had it, could break any cryptographic system ever devised.

If $\mathcal{P} = \mathcal{NP}$, the proof would be the most consequential piece of mathematics ever written.

---

Why Nobody Has Proved It

When I first read about this problem, I assumed the reason no one had solved it was effort. That it just needed more researchers, more time, more compute. A harder version of a normal problem.

That is not what is happening.

The difficulty is not that the proof is long and tedious. The difficulty is that nobody knows what shape a proof would even take. Every known proof technique, when applied to P vs NP, runs into a wall. Not a wall you can push through if you are clever enough. A wall that has been proven to be there.

Three barriers have been formally identified, and we will examine each one carefully in Phase 4. For now the short version: the Relativization Barrier rules out classical diagonalization approaches. The Natural Proofs Barrier rules out a broad family of combinatorial arguments. The Algebrization Barrier rules out most strategies that algebraically extend computations.

A correct proof of P vs NP will require a technique that does not yet exist. That is not pessimism. That is just where the math currently stands.

---

The Asymmetry Nobody Tells You About

The two possible answers are not symmetric in what proving them would require.

To prove $\mathcal{P} = \mathcal{NP}$, you need to construct one polynomial-time algorithm for any single NP-Complete problem. One algorithm. Show it works. Done. The proof is constructive: you exhibit the object.

To prove $\mathcal{P} \neq \mathcal{NP}$, you need to show that no polynomial-time algorithm exists for certain problems. Not just that none has been found. That none could ever exist. You need to rule out every algorithm that anyone could conceive of, across all of mathematics and all of time. That is not a statement about one object. It is a statement about an infinite class of non-objects.

Proving impossibility is categorically harder than proving existence.

This does not make P = NP the more likely answer

The asymmetry is about proof difficulty, not about which answer is true. Almost every researcher in complexity theory believes $\mathcal{P} \neq \mathcal{NP}$. We have hundreds of NP-Complete problems, each studied for decades, none of which has yielded a polynomial-time algorithm. If a general shortcut existed, someone would probably have found a trace of it by now.

But "almost everyone believes X" is not a proof. The problem remains open.

---

The Question Underneath the Question

Here is the thing I keep coming back to. The one that made P vs NP feel like more than a computer science problem to me.

What the question is really asking is whether recognizing a correct answer is fundamentally easier than finding one.

Think about it outside of computing for a moment. When you hear a piece of music that is exactly right, you know it. That recognition is instant. But composing that piece is not the same experience at all.

If $\mathcal{P} = \mathcal{NP}$, that gap collapses mathematically. Recognition and creation become equivalent. Knowing what good looks like would be enough to produce it. If $\mathcal{P} \neq \mathcal{NP}$, the gap is real and permanent. There is something irreducible about finding an answer that no amount of fast verification can substitute for.

I do not know which answer is true. Nobody does. But that question is part of why I started writing this series in the first place.

---

Phase 1 Is Complete

Here is what we now have:

• A precise model of computation
• A precise measure of efficiency
• Formal definitions of $\mathcal{P}$ and $\mathcal{NP}$
• The central question, clearly stated
• An honest account of why the question is hard

Phase 2 builds the next layer. It introduces NP-Complete problems: the hardest problems inside $\mathcal{NP}$, the ones where solving any single one in polynomial time would immediately solve all of them. Sudoku, TSP, graph coloring, circuit satisfiability are all connected, and the mechanism that connects them is one of the most remarkable results in all of computer science.

That mechanism is called a reduction. It is what Post 11 is about.

What We Have Established

$\mathcal{P} \subseteq \mathcal{NP}$ is proven. Whether $\mathcal{P} = \mathcal{NP}$ or $\mathcal{P} \neq \mathcal{NP}$ is unknown. Almost all researchers believe the classes are strictly separate, but no proof exists in either direction. Every known proof technique fails for formal mathematical reasons. The question remains the most important open problem in computer science.

See you in Phase 2. 🚀

---

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