The Algorithm Maze: Why Checking an Answer Is Easier Than Finding It

A human-friendly journey into P vs NP, the million-dollar question behind cryptography, AI, biology, and the limits of discovery.

---

Imagine a dinner with 100 guests

You are hosting a dinner for 100 guests.

You have 10 round tables. Some guests cannot sit together because they hate each other. Some must sit near each other because they are family, investors, partners, or people you really do not want to offend.

You need a seating plan that satisfies every rule.

Now imagine two situations.

In the first situation, someone hands you a complete seating chart. You check the guest list. You scan the conflict rules. You verify that every table obeys the constraints. Annoying, yes. But doable.

In the second situation, nobody gives you anything. You must create the seating chart from scratch.

That is a completely different beast.

Even if you ignore the round-table details and simply arrange 100 people in a line, the number of possible arrangements is:

$$100! \approx 9.33 \times 10^{157}$$

That is not “large” in the everyday sense. That is absurdly large. It is far beyond anything brute force can touch.

This gap between checking a solution and finding a solution is the heart of one of the deepest open problems in mathematics and computer science:

$$P \text{ vs } NP$$

The Clay Mathematics Institute describes the core question simply: if a solution is easy to check, is it also easy to find? P vs NP is one of the seven Millennium Prize Problems, each with a prize of USD 1 million for a correct solution.¹²

This is not just a puzzle for computer scientists. It sits under modern encryption, automated theorem proving, logistics, drug discovery, artificial intelligence, chip design, economics, and the philosophy of creativity.

At its deepest level, P vs NP asks:

Is every act of discovery just verification in disguise?

---

“Fast” does not mean seconds. It means growth.

When computer scientists ask whether a problem is “easy,” they do not mean easy for a laptop today. They mean something more structural:

How does the work grow as the input grows?

Let the input size be (n). For example:

• (n) cities in a route-planning problem.
• (n) variables in a logical formula.
• (n) guests in a seating problem.
• (n) items in a knapsack.

An algorithm has a running time (T(n)). We care about the shape of (T(n)).

If:

$$T(n) = O(n)$$

the work grows linearly.

If:

$$T(n) = O(n^2)$$

the work grows quadratically.

If:

$$T(n) = O(n^k)$$

for some fixed constant (k), the algorithm runs in polynomial time.

That is the formal version of “efficient” in classical complexity theory.

But if:

$$T(n) = O(2^n)$$

or:

$$T(n) = O(n!)$$

the work explodes.

Here is the intuition.

At one microsecond per operation, (n^2) for (n=100) takes:

$$100^2 = 10{,}000$$

microseconds, or about 0.01 seconds.

But (2^{100}) operations takes:

$$2^{100} \approx 1.27 \times 10^{30}$$

microseconds, which is roughly:

$$4 \times 10^{16}$$

years.

And (100!) is much worse.

That is the difference between “done before coffee” and “not done before the heat death of the universe.”

This is why polynomial time became the mathematical proxy for feasible computation. Stephen Cook’s official Clay problem statement defines (P) as the class of languages decidable by a Turing machine in polynomial time.³

---

Class P: problems we know how to solve efficiently

A problem is in P if there exists a deterministic algorithm that solves it in polynomial time.

Formally:

$$P = \{L \mid L \text{ can be decided by a deterministic machine in polynomial time}\}$$

Plain English:

A problem is in P if a normal computer can solve it by following a reliable step-by-step method whose running time grows like:

$$n,\quad n^2,\quad n^3,\quad n^{10}$$

or another fixed polynomial.

Examples include:

• Sorting a list.
• Multiplying two numbers.
• Finding the shortest path in many graph settings.
• Checking whether a number is prime.
• Searching a sorted database.

These problems can still be hard in practice if (n) is huge or the polynomial degree is ugly. An (n^{100}) algorithm is technically polynomial but useless in real life.

Still, P captures something important:

routine computability.

It is the world of problems where we have an efficient recipe.

---

Class NP: problems where answers are easy to verify

Now comes the more interesting class: NP.

NP does not mean “not polynomial.” That is a common misunderstanding.

NP stands for nondeterministic polynomial time, but the most useful modern way to think about it is:

A problem is in NP if, whenever the answer is “yes,” someone can give you a short certificate that lets you verify the answer in polynomial time.

Formally:

$$L \in NP$$

if there exists a polynomial-time verifier (V) and a polynomial (p) such that:

$$x \in L \iff \exists y,\ |y| \le p(|x|),\ V(x,y)=1$$

Plain English:

Input (x) is a yes-instance if and only if there exists some certificate (y), not too long, that convinces a fast checker (V).

Think of a math exam.

Solving the problem from scratch may take hours. But if a student gives the full proof, the teacher can check each step much faster than discovering the proof herself.

That proof is the certificate.

In the seating-chart story, the certificate is the seating plan.

In Sudoku, the certificate is the completed grid. Important detail: the formal complexity example is generalized Sudoku, where the board size grows. A fixed 9×9 Sudoku board has only finitely many possible boards, so it is not the real asymptotic object.

In cryptography, the certificate might be a secret key.

In route planning, the certificate might be a proposed route.

In logic, the certificate might be a truth assignment that makes a formula true.

Cook’s formal definition of NP uses exactly this verifier/certificate structure: a language is in NP if membership can be witnessed by a string (y) of polynomial length and checked by a polynomial-time relation.³

---

Why P is automatically inside NP

Every problem in P is also in NP.

Why?

Because if you can solve a problem quickly, you can also verify a proposed answer quickly.

The verifier can simply ignore the certificate and run the fast solver.

So:

$$P \subseteq NP$$

That part is not controversial. Cook’s official statement also notes that (P \subseteq NP) is trivial.³

The real question is whether the containment is strict.

$$P = NP?$$

or:

$$P \ne NP?$$

In plain language:

Is finding always as easy as checking?

Most researchers believe the answer is no. But nobody has proved it.

---

SAT: the first master puzzle

To understand P vs NP, you need to meet SAT.

SAT stands for Boolean satisfiability.

You are given a formula made of variables that can be either true or false:

$$x_1, x_2, x_3, \ldots, x_n$$

The formula uses logical operations such as AND, OR, and NOT.

Example:

$$(x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_4) \land (x_2 \lor x_5)$$

The question is:

Is there some assignment of true/false values that makes the whole formula true?

If there are (n) variables, brute force tries:

$$2^n$$

assignments.

For (n=100), that is already impossible by direct search.

But if someone gives you one assignment, checking it is easy. Plug in the values. Evaluate the formula. Done.

That means SAT is in NP.

Then came the breakthrough.

In 1971, Stephen Cook proved that SAT is not just in NP. It is NP-complete. Cook showed that the computation of any polynomial-time verifier can be encoded as a Boolean formula, so solving SAT efficiently would solve every problem in NP efficiently.³

That is the moment P vs NP became a precise battlefield.

SAT became the universal maze.

---

Reductions: how one hard problem becomes every hard problem

The key tool is called a reduction.

A reduction means:

“I may not know how to solve problem A, but I can efficiently translate it into problem B. So if you solve B, I can solve A.”

Formally, problem (A) reduces to problem (B) in polynomial time if there is a polynomial-time function (f) such that:

$$x \in A \iff f(x) \in B$$

We write:

$$A \le_p B$$

Now define NP-complete.

A problem (B) is NP-complete if:

1. (B \in NP)
2. Every problem (A \in NP) reduces to (B):

$$\forall A \in NP,\ A \le_p B$$

So if an NP-complete problem is in P, then every NP problem is in P.

$$B \in P \text{ and } B \text{ is NP-complete} \Rightarrow P = NP$$

This is why NP-complete problems matter so much. They are not just hard-looking puzzles. They are mathematically connected.

After Cook proved SAT was NP-complete, Richard Karp showed that many famous combinatorial problems are equivalent in this deep sense: either all of them have polynomial-time algorithms, or none of them do.⁴

Examples include:

• Traveling Salesman, in its decision form.
• Graph coloring.
• Clique.
• Vertex cover.
• Knapsack, in its decision form.
• Scheduling problems.
• Logical satisfiability.

A useful distinction:

NP-complete usually refers to decision problems: yes/no questions.

NP-hard means at least as hard as every problem in NP, but the problem may not itself be in NP. Optimization versions are often NP-hard. For example, “find the shortest possible route” is an optimization problem; “is there a route of length at most (K)?” is the decision version.

This distinction matters. It keeps the math clean.

---

The traveling salesman: easy to check, hard to find

Suppose a salesperson must visit (n) cities and return home.

The decision version asks:

Is there a tour with total length at most (K)?

If someone gives you a route, you check:

1. Does it visit every city exactly once?
2. Does it return home?
3. Is the total distance (\le K)?

That is easy.

But finding the route from scratch may require searching among roughly:

$$(n-1)!$$

possible tours, depending on symmetries.

That factorial explosion is why the traveling salesman problem became one of the iconic examples of computational hardness.

Real logistics companies do not simply brute-force all routes. They use heuristics, approximations, relaxations, constraints, branch-and-bound, and domain-specific tricks.

That is an important real-world lesson:

P vs NP is about worst-case mathematical possibility. Practical engineering often survives by exploiting structure.

---

If P=NP, the world changes - but not magically

Now imagine someone proves:

$$P = NP$$

What happens?

The honest answer depends on what kind of proof it is.

If the proof is nonconstructive, or the algorithm has running time like:

$$n^{10{,}000}$$

then the theoretical world changes, but your laptop does not suddenly become a god.

But if the proof gives a practical algorithm for SAT or another NP-complete problem, everything changes.

A practical SAT solver that works in guaranteed polynomial time for all cases would become a universal engine for search.

You could express a goal as constraints:

• This drug molecule must bind here.
• This circuit must satisfy these timing rules.
• This schedule must avoid these conflicts.
• This proof must follow these axioms.
• This design must meet this performance target.

Then the machine would find the object, not just check it.

This is why P=NP is sometimes described as collapsing the gap between creativity and verification.

Cook’s official problem statement notes that a practical algorithm for an NP-complete problem would have devastating consequences for cryptography, but also positive consequences: it could transform mathematics by finding formal proofs of any theorem with a proof of reasonable length, and similar comments apply to design, physical theories, and even music, provided we can efficiently recognize a good result.³

That last phrase is critical:

provided we can efficiently recognize a good result.

P=NP would not automatically produce beauty, wisdom, taste, or truth in domains where we cannot define a verifier.

But anywhere we can define a fast checker, P=NP would be revolutionary.

---

Cryptography: the glass-vault problem

Modern digital security depends on asymmetry.

Multiplying two huge primes is easy.

Factoring their product is believed to be hard.

Computing a public-key operation is easy.

Reversing it without the secret is believed to be hard.

That is the structure behind much of public-key cryptography.

If P=NP with a practical algorithm, many complexity-based cryptographic assumptions collapse. Cook’s statement explicitly notes that if P=NP, assumptions such as the difficulty of integer factoring or breaking DES-style cryptographic systems would fail; he gives the example that a fast algorithm for 3-SAT could be used to factor large numbers.³

But be precise.

P=NP would not mean “all secrecy is impossible.” Information-theoretic systems, such as a properly used one-time pad, are not based on computational hardness. Physical assumptions and some quantum protocols are a separate story.

Still, the practical internet would be forced through a brutal redesign.

Banking, signatures, blockchain systems, identity, secure messaging, software updates, military communications - all of them rely heavily on computational hardness.

If that hardness disappears, the locks become glass.

---

Biology: protein folding and the limits of search

Proteins are chains of amino acids. Their function depends heavily on their three-dimensional shape.

One way to frame protein folding is:

Given a sequence, find a low-energy conformation.

This sounds like a physics problem, but it also becomes a search problem. The protein has many possible shapes. The “right” one is often modeled as a low-energy state.

Formalized protein-folding models have been shown to be NP-hard. A classic paper by Unger and Moult proved NP-hardness for finding the lowest free-energy conformation in a lattice model, and later work studied robust NP-hardness across broader lattice and energy settings.⁵⁶

This does not mean P=NP would instantly solve all of biology.

Real proteins are physical systems. They involve continuous geometry, solvent effects, kinetics, measurement error, cellular environments, and evolutionary history. AlphaFold-style systems also do not solve arbitrary NP-hard optimization problems in the theoretical sense; they use learned structure from biological data.

But a practical P=NP breakthrough would still be massive.

Many search and optimization subproblems in biology, chemistry, and drug design would become far more tractable. Instead of testing enormous spaces of candidates, we could encode constraints and search directly.

The dream version is not “biology solved.”

The realistic version is:

many impossible design loops become computable.

---

AI and creativity: the uncomfortable part

A lot of AI can be viewed as search.

Find a model that explains the data.

Find a program that generates the examples.

Find a policy that gets high reward.

Find a proof.

Find a design.

Find a plan.

If we can verify that a candidate model performs well, then model search starts to look NP-like.

A rough version of the learning problem is:

Given data (D), find a small program (P) such that:

$$P(x_i) = y_i$$

for all examples ((x_i, y_i)).

Checking a proposed program against the dataset is easy. Finding the smallest such program is hard.

This connects to Occam’s razor: prefer the simplest explanation that fits the data.

In a practical P=NP world, “find the simplest explanation” becomes less philosophical and more computational.

But again, there is a hard boundary.

P=NP helps when the goal can be verified.

It does not solve vague goals like:

• “Write a moving novel.”
• “Make a beautiful film.”
• “Build a meaningful company.”
• “Discover what humans should value.”

Unless those goals are translated into a verifier, P=NP has nothing exact to optimize.

So the philosophical version is seductive but dangerous.

A better statement is:

P=NP would automate any creative task whose success condition can be checked efficiently and formally.

That is still enormous.

---

Physics, materials, and optimization

Many physical systems can be written as energy-minimization problems.

Find the configuration with the lowest energy.

Find the stable state.

Find the optimal structure.

Spin glasses, Ising models, materials design, chip layouts, and molecular systems often contain enormous combinatorial search spaces.

This is why P vs NP touches physics and engineering. It is not because nature runs SAT solvers. It is because many of our models of nature become optimization problems.

If P=NP with a practical algorithm, whole categories of simulation and design would change.

Better batteries.

New materials.

Improved chips.

More efficient logistics.

Better schedules.

Cleaner supply chains.

But the same caveat stays alive:

formal solvability does not remove modeling error.

If your constraints are wrong, a perfect optimizer gives you the perfect answer to the wrong question.

---

Impagliazzo’s five worlds: maybe worst-case hardness is not enough

Russell Impagliazzo gave a useful way to think about possible computational universes.

The question is not only whether P=NP. It is also whether hard problems are hard in real life, on average, and whether that hardness can support cryptography.

His five “worlds” are:

Algorithmica: NP is easy in the worst case. This is the P=NP-style world. Search collapses.

Heuristica: NP is hard in the worst case but easy on average. The monster exists, but normal life rarely meets it.

Pessiland: hard average-case problems exist, but not in a way that gives us cryptography. This is the miserable world: enough hardness to block algorithms, not enough useful structure to secure secrets.

Minicrypt: one-way functions exist, so private-key cryptography and related primitives can exist, but public-key cryptography is impossible.

Cryptomania: public-key cryptography is possible. This is the world modern internet security hopes we live in.

Impagliazzo’s original paper introduced these five possible worlds to show how average-case complexity shapes algorithm design, cryptography, and security.⁷

This framing matters because P≠NP alone is not enough for cryptography.

Cryptography needs hard problems that remain hard on average, not just carefully constructed worst-case monsters.

---

Why most experts believe P≠NP

There is no proof.

But the expert consensus leans heavily toward:

$$P \ne NP$$

The reason is not just “vibes.”

For more than 50 years, researchers have attacked thousands of NP-complete problems from every angle: algorithms, logic, combinatorics, optimization, circuit complexity, proof theory, SAT solving, machine learning, quantum computation, and more.

No one has found a worst-case polynomial-time algorithm for any NP-complete problem.

That failure is evidence, not proof.

A 2019 poll by William Gasarch reported that 109 out of 124 respondents, about 88%, believed P≠NP; among people classified as experts who had seriously thought about the problem, the answer was 99% no to P=NP.⁸

The intuition is simple:

Checking a path through a maze is not the same as finding the path.

Checking a proof is not the same as discovering the proof.

Checking a molecule is not the same as designing the molecule.

Checking a strategy is not the same as inventing the strategy.

The world seems to reward search, creativity, and accumulated structure because they are genuinely scarce.

P≠NP formalizes that scarcity.

But intuition is not proof.

And that is where the real difficulty begins.

---

Why proving P≠NP is brutally hard

If P≠NP feels so obviously true, why can’t we prove it?

Because the usual proof methods hit walls.

Not psychological walls. Formal walls.

Complexity theory has discovered several “barriers” showing that broad families of proof techniques cannot resolve P vs NP.

These barriers are not failures. They are maps of failure.

They tell us what a successful proof cannot look like.

---

Barrier 1: relativization

An oracle is a magical black box that answers a specific kind of question instantly.

We can imagine giving both P-machines and NP-machines access to the same oracle (A). Then we study:

$$P^A$$

and:

$$NP^A$$

Baker, Gill, and Solovay showed that there are relativized worlds where:

$$P^A = NP^A$$

and other relativized worlds where:

$$P^B \ne NP^B$$

Aaronson and Wigderson summarize the implication clearly: because some relativized worlds have P=NP and others have P≠NP, any proof of the real P vs NP question must use non-relativizing techniques, meaning techniques that exploit properties of computation not preserved under arbitrary oracles.⁹

Translation:

A proof method that works the same even after adding any magical black box cannot solve P vs NP.

This killed a huge class of diagonalization-style arguments.

---

Barrier 2: natural proofs

After relativization, researchers turned to circuit complexity.

Instead of studying machines over time, study Boolean circuits.

Maybe we can prove that SAT requires huge circuits. If SAT needs super-polynomial-size circuits, then SAT is not in P, and P≠NP.

This sounded promising.

Then Razborov and Rudich introduced the natural proofs barrier.

Very roughly, many circuit lower-bound proofs work by finding a broad property that:

1. Is easy to recognize.
2. Holds for many random functions.
3. Does not hold for simple circuits.

That kind of proof is “natural.”

Razborov and Rudich argued that known lower-bound proofs fit this natural pattern and showed, under standard cryptographic hardness assumptions, that natural proofs cannot prove super-polynomial lower bounds for general circuits.¹⁰

Why?

Because a strong natural proof would also distinguish random functions from pseudorandom functions.

But pseudorandom functions are exactly the kind of objects cryptography depends on.

So a natural proof strong enough to separate P from NP would also threaten the cryptographic hardness assumptions we believe.

In plain language:

A proof that is too broad becomes a codebreaker.

---

Barrier 3: algebrization

Then came arithmetization.

Researchers learned to convert Boolean logic into polynomials over finite fields. This helped prove major results in interactive proofs, including IP=PSPACE.

Maybe algebra could break the P vs NP wall.

Aaronson and Wigderson showed that even this has limits. They introduced algebrization, a barrier showing that many algebraic techniques still cannot resolve major open problems such as P vs NP. Their paper states that P vs NP and related problems will require non-algebrizing techniques.⁹

So the proof must avoid three traps:

• It cannot be merely relativizing.
• It cannot be a standard natural proof.
• It cannot be only an algebrizing argument.

That is why P vs NP is not just unsolved.

It is protected by decades of failed-proof archaeology.

---

Where research is going now

Modern work is not just “try harder at SAT.”

The field has become more self-aware. Researchers now study the complexity of complexity itself.

Three directions matter.

---

1. Geometric Complexity Theory

Geometric Complexity Theory, introduced by Mulmuley and Sohoni, tries to use algebraic geometry and representation theory to prove lower bounds.

Instead of treating computation only as logic or circuits, it studies computational problems as geometric objects.

A 2025 Theory of Computing survey describes GCT as an approach to proving lower bounds in algebraic complexity theory using algebraic geometry and representation theory. It also notes that the area has gained momentum but has a steep learning curve because it draws from many parts of mathematics.¹¹

This is not a near-term magic bullet. It is a deep program.

But P vs NP probably requires math that does not yet feel ordinary.

GCT is one attempt to build that math.

---

2. Meta-complexity and MCSP

Meta-complexity asks:

How hard is it to determine how hard a function is?

The key problem here is the Minimum Circuit Size Problem, or MCSP.

Given the full truth table of a Boolean function, MCSP asks:

What is the smallest circuit that computes this function?

That sounds meta because it is.

You are not solving a normal problem. You are measuring the complexity of a function itself.

The Simons Institute describes meta-complexity as the study of computational tasks that are themselves about computations and their complexity, with MCSP and time-bounded Kolmogorov complexity as key examples. It also notes connections to proof complexity, cryptography, and learning theory.¹²

This is one of the most active modern angles because it connects multiple hard areas at once.

---

3. Kolmogorov complexity and one-way functions

Kolmogorov complexity asks:

What is the length of the shortest program that outputs a given string?

A string like:

00000000000000000000

has low Kolmogorov complexity.

A truly random-looking string usually has high Kolmogorov complexity because there is no shorter description than the string itself.

Time-bounded Kolmogorov complexity adds a constraint:

The program must produce the string within a given time limit.

Yanyi Liu and Rafael Pass proved a major connection between one-way functions and time-bounded Kolmogorov complexity. Their arXiv abstract states that the existence of one-way functions is equivalent to mild average-case hardness of time-bounded Kolmogorov complexity, and that this characterizes central private-key cryptographic primitives.¹³

This is important because one-way functions are the foundation of much of cryptography.

If we understand exactly when one-way functions exist, we understand when secure computation is possible.

That is not directly a proof of P≠NP, but it attacks the same deep territory: the structure of computational hardness.

---

What P vs NP really says about the world

P vs NP is often explained as a computer science problem.

That is too small.

It is a question about search.

Can every searchable universe be navigated efficiently if we can recognize the destination?

Can every proof be found as easily as it can be checked?

Can every design be generated as easily as it can be evaluated?

Can every hidden structure be discovered just because we can verify it once seen?

If P=NP, then the universe is hiding a general shortcut.

If P≠NP, then search has irreducible cost.

The second option matches our experience.

Science is slow.

Evolution is slow.

Mathematics is hard.

Engineering is iterative.

Companies do not find perfect strategies by verification alone.

Humans do not become Mozart because they can recognize a good melody.

They do not become Gauss because they can follow a proof.

They do not become great founders because they can recognize a good product after it exists.

Creation and recognition feel different because maybe, mathematically, they are different.

P vs NP asks whether that feeling is a theorem.

So far, we do not know.

---

Mini-glossary

P: Problems solvable in polynomial time by a deterministic algorithm.

NP: Problems whose yes-answers can be verified in polynomial time using a certificate.

Certificate: A proposed solution or witness that lets a verifier check correctness quickly.

Verifier: An algorithm that checks a certificate.

Polynomial time: Running time bounded by (O(n^k)) for some constant (k).

Exponential time: Running time like (O(2^n)), which becomes infeasible quickly.

Reduction: A polynomial-time translation from one problem to another.

NP-complete: The hardest problems inside NP. If any NP-complete problem is in P, then P=NP.

NP-hard: At least as hard as every problem in NP, but not necessarily itself in NP.

SAT: Boolean satisfiability, the first known NP-complete problem.

Oracle: A hypothetical black box that answers a chosen problem instantly.

Relativization: A proof behavior that remains valid even when all machines get the same oracle.

Natural proof: A broad, constructive circuit lower-bound strategy that is blocked by connections to pseudorandomness.

Algebrization: A barrier showing that many algebraic extensions of relativizing methods still cannot resolve P vs NP.

One-way function: A function that is easy to compute but hard to invert.

Kolmogorov complexity: The length of the shortest program that outputs a string.

Meta-complexity: The study of the complexity of problems that ask about complexity itself.

---

Final takeaway

P vs NP is the cleanest version of a brutal question:

Is finding fundamentally harder than checking?

Everything else is downstream.

Cryptography depends on “yes.”

Creativity feels like “yes.”

Science behaves like “yes.”

But mathematics has not proved “yes.”

Until it does, the maze remains open.

And somewhere inside that maze is either a universal shortcut - or the proof that no such shortcut can exist.

Footnotes

1. Clay Mathematics Institute, “The P versus NP Problem”: https://www.claymath.org/millennium/p-vs-np/ ↩

2. Clay Mathematics Institute, “Millennium Prize Problems”: https://www.claymath.org/millennium-problems/ ↩

3. Stephen Cook, “The P versus NP Problem,” official Clay problem statement PDF: https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

4. Richard M. Karp, “Reducibility among Combinatorial Problems”: https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9 ↩

5. Unger and Moult, “Finding the lowest free energy conformation of a protein is an NP-hard problem”: https://pubmed.ncbi.nlm.nih.gov/8281131/ ↩

6. “Robust proofs of NP-hardness for protein folding”: https://pubmed.ncbi.nlm.nih.gov/9109034/ ↩

7. Russell Impagliazzo, “A Personal View of Average-Case Complexity”: https://www.cs.mun.ca/~kol/courses/6743-w15/papers/russell-fiveworlds.pdf ↩

8. William Gasarch, “The Third P =? NP Poll”: https://www.cs.umd.edu/users/gasarch/papers/poll3.pdf ↩

9. Scott Aaronson and Avi Wigderson, “Algebrization: A New Barrier in Complexity Theory”: https://www.scottaaronson.com/papers/alg.pdf ↩ ↩²

10. Alexander Razborov and Steven Rudich, “Natural Proofs”: https://mit6875.github.io/PAPERS/natural_proofs.pdf ↩

11. Theory of Computing, “Geometric Complexity Theory” survey: https://theoryofcomputing.org/articles/gs010/gs010.pdf ↩

12. Simons Institute, “Meta-Complexity”: https://simons.berkeley.edu/programs/Meta-Complexity2023 ↩

13. Yanyi Liu and Rafael Pass, “On One-Way Functions and Kolmogorov Complexity”: https://arxiv.org/abs/2009.11514 ↩