Cognitive One-Way Functions
The core idea
Some processes are easy to run in one direction and hard to run in the other. Mix yellow and blue paint and you get green in a second. Hand someone a can of green paint and ask which yellow and which blue, in what proportions, produced it, and the question becomes close to impossible. The forward step is cheap; the reverse step is expensive. That asymmetry is the whole idea behind a one-way function, and it turns out to describe a surprising amount of both cryptography and cognition.
This document traces the idea across three settings that share the same shape: cryptographic one-way functions, cognitive and perceptual asymmetries, and the way modern AI exploits the gap between solving a problem and checking a solution.
1. The cryptographic original
In computer science, a one-way function is easy to compute forward and infeasible to invert. Two standard examples anchor the concept.
Multiplying two large primes is fast. Recovering those two primes from the product alone (factorization) is, for large enough numbers, computationally out of reach with current methods. Cryptographic hash functions such as SHA-256 behave the same way: computing the hash of a message is instant, but finding a message that produces a given hash is not.
Three properties define the class:
- Easy to compute in the forward direction (polynomial time).
- Infeasible to reverse (effectively exponential effort).
- Small changes to the input produce large, unpredictable changes in the output.
These properties are what make password hashing, digital signatures, public-key cryptography, and message authentication possible. The security rests entirely on the direction being hard to run backward.
2. The cognitive parallel
Human cognition is full of the same asymmetry. In each pair below, one direction is nearly effortless and the other is much harder, even though both concern the "same" information.
| Domain | Easy direction | Hard direction |
|---|---|---|
| Faces | Recognizing a familiar face instantly | Drawing or describing that face from memory |
| Language | Understanding speech in your native tongue | Producing fluent, correct speech (visible in child development) |
| Melody | Recognizing a familiar tune | Singing it back accurately |
| Patterns | Spotting a pattern in data or images | Creating a novel pattern that looks natural |
| Humor | Finding something funny | Writing original material that lands |
| Time | Feeling time pass in the moment | Estimating how long something took |
| Movement | Recognizing someone's gait | Describing or reproducing that movement |
The cleanest instance of the pattern is recognition versus recall, which gets its own treatment in the companion document. In short: picking the right answer from a list is easy and accurate; producing it from memory with no cue is effortful and error-prone. This is why multiple-choice tests feel easier than free response, why a password is easier to verify than to guess, and why a song's name escapes you until the song starts playing.
3. Generation is hard, verification is easy
Stated more generally: for many tasks, producing a valid answer is expensive but checking a proposed answer is cheap.
| Domain | Hard: generate | Easy: verify |
|---|---|---|
| Memory | Recall a word from context | Recognize it among options |
| Vision | Imagine a realistic face | Judge whether a face looks real |
| Language | Write a coherent story | Judge whether a story is coherent |
| Math | Produce a proof | Check that a proof is valid |
| Machine learning | Generate an image from noise | Discriminate real from fake |
| Cryptography | Find a hash preimage | Confirm a hash matches |
Every row shares the same structure. Generation is a search over a vast combinatorial space. Verification checks a small set of conditions. If you let f be a generator producing candidate outputs y, and g be an evaluator that returns whether y is acceptable, then generation means searching for a y with g(y) true, while verification means simply computing g(y). The first is hard because g may not be cleanly invertible; the second is a direct function evaluation.
This is the same asymmetry that sits at the center of the P versus NP question: given a candidate solution, checking it can be fast even when finding it is not.
4. Why this matters for AI
The generation/verification gap is not just an observation about difficulty. It is a lever, and recent AI progress leans on it directly. The argument, drawn from Andrej Karpathy's "you can automate what you can verify" framing and Subbarao Kambhampati's response to it, runs as follows.
If you can verify a solution, you can often train a model to produce solutions, regardless of how hard producing them is. The mechanism is generate-and-test: a base model proposes many candidate answers, a verifier checks which ones pass, and reinforcement learning gradually compiles the verifier's signal back into the model so it produces passing answers more often. This is the idea behind reinforcement learning with verified rewards (RLVR).
The shape of the verifier's signal, not only its existence, decides whether learning is feasible. A verifier that returns a graded score gives the search a gradient to climb, so it converges fast. A verifier that returns only a bare pass or fail gives almost no gradient, so the same search collapses toward brute force. A good illustration is a hidden-code game: if the verifier reports how many symbols are exactly right and how many are the right symbol in the wrong place, an agent cracks the code in a handful of guesses; if the verifier reports only "solved or not," the agent has to grind through nearly the whole space. Same problem, same verifier availability, radically different difficulty, purely because of how much information the reward carries. Designing a dense, well-shaped verifiable reward is therefore as much of the work as having a verifier at all.
Two clarifications keep the framing accurate.
First, this is not the same as the P-versus-NP distinction, and calling it so is misleading. NP is defined by polynomial-time verification, but nothing stops this training loop from using verifiers whose own checking is more expensive than that. Systems already do well on problems whose verification is not polynomial-time (some planning problems, formal-proof checking whose cost scales with proof length).
Second, a better analogy than complexity classes is the shift from imperative to declarative programming. Imperative programming describes how to do something step by step, like a recipe: crack the eggs, beat for thirty seconds, heat the pan. Declarative programming describes what you want: fluffy, slightly runny scrambled eggs. Using a verifier to shape a model's output is a move toward the declarative style. You specify the goal through the verifier rather than hand-writing the procedure.
The practical takeaway inverts the usual instinct. Do not focus first on how hard a problem is to solve. Focus on how hard it is to check, because verifiability is what makes a problem trainable.
5. The boundary of the approach
The verifier trick has a ceiling. Verifiers are written by humans, and reinforcement learning over them compiles human-provided knowledge into the model, exactly as reinforcement learning over a simulator compiles the simulator's knowledge. That makes these systems strong force multipliers over what humanity already knows, whether that knowledge is stated as facts or encoded as verifiers. It does not, on its own, push past humanity's existing knowledge. Generating many candidate ideas is only one part of discovery; an agent that is meant to find genuinely new things also has to act in the world and learn from the results, which is harder and riskier than learning secondhand from data or simulators. The reasonable position is that models can accelerate discovery without, by themselves, replacing the part of science that requires contact with reality.
6. A related thread: outsourcing cognition upward
The same forward-easy / reverse-hard logic connects to a broader pattern in how tools change what humans have to think about. Each layer of technology takes over one dimension of difficulty and lets people work one level more abstractly. The progression runs from offloading muscle to offloading meaning to offloading whole conceptual layers.
| Level | What gets outsourced | What the human now focuses on |
|---|---|---|
| 1 | Motor control (levers, autofocus, anti-lock brakes) | Intent, not execution physics |
| 2 | Sensory processing (thermostats, GPS, OCR) | Representations, not raw signals |
| 3 | Procedure (spreadsheets, CNC, search) | What to do, not how |
| 4 | Pattern recognition (spellcheck, regression, recommenders) | Which patterns matter |
| 5 | Simulation (climate models, CAD, theorem provers) | Model structure, not computation |
| 6 | Creation (LLMs, generative design, agents) | Guiding and curating |
| 7 | Reflection (explainability, hypothesis generators) | Reasoning about reasoning |
The computing stack is the purest version of this. Each layer, from electrons through logic gates, assembly, high-level languages, libraries, machine-learning models, and up to natural-language interfaces, frees the person above it from one dimension of causal detail while keeping control. Abstraction, in this sense, is compression plus control: it reduces how much state you must track while keeping the interface expressive.
There is a catch worth stating plainly. Each higher level gains autonomy from the one below, but never independence. The lower levels remain the substrate. Forgetting them produces predictable failures: software that scales logically but melts physically, financial models that ignore the real economy, theories that are internally elegant but empirically untethered, language that refers only to more language. Strong reasoning moves up for generalization and back down for grounding, rather than settling permanently at the top.
This connects back to the main theme. Verification, grounding, and checking against a lower level are all the "easy direction." Generation, abstraction, and building upward are the "hard direction." The systems that stay reliable are the ones that keep running both.