The sealed rule

A teacher has a Boolean rule sealed in an envelope. It decides whether each of eight three-bit cards belongs to a concept. The learner may see four cards that the teacher calls positive. Every one has first bit 1. Is the hidden rule simply “first bit is 1”? It might instead require the first bit and permit only three of the four unseen combinations. It might contain an exception that no observed card triggers. The data do not carry their own guarantee of generalisation.

One response is to demand the exact rule. That replaces learning with transmission. Another is to accept any guess that fits the four cards. That gives no reason to trust the next card. Valiant’s paper works between those extremes. It asks what a learner can deduce when the teacher supplies examples through a restricted channel, the target comes from a named representation class, the observations follow an arbitrary but fixed distribution, and every important cost must grow only polynomially.

The move resembles Church and Turing’s earlier formalisation of computation. Their models did not explain every physical act of calculating. They isolated a stable question that could support proofs. Valiant attempts the analogous move for learning. A recognition program counts as learned when it is acquired without being passed instruction by instruction. The paper then narrows attention to propositional concepts and asks which classes admit feasible deduction procedures.

The information contract

Valiant uses t Boolean variables. An input vector assigns each variable 0, 1 or *. The star means undetermined. A vector is total when it contains no stars. A Boolean function on total vectors becomes a concept on partial vectors by a demanding rule: the concept is positive on a partial vector only if every compatible total completion is positive. Thus the partial vector (1,*,0) is not merely a missing-data record. It is a compact claim that all ways of filling the middle bit satisfy the concept.

The learning protocol offers two routes to information. EXAMPLES returns a positive vector drawn independently from an arbitrary distribution D over positive vectors. ORACLE takes a vector chosen by the learner and answers whether the target concept is positive there. The paper later introduces stronger queries for read-once expressions, but these two operations carry its central algorithms.

The definition of learnability then binds four quantities. The learner must run in time polynomial in the number of variables, the size parameters of the target representation and an adjustable accuracy parameter h. With probability at least 1−1/h, it must output a recogniser g that never accepts when the target f would not, while rejecting at most 1/h of the positive probability mass. Valiant notes that two independent parameters would be more precise. In later notation one would separate failure probability δ from tolerated error ε. The 1984 statement effectively sets both to 1/h.

Why the stars are structural, not missing values

The paper’s partial vectors solve a problem created by a large vocabulary. A concept may depend on only a few propositions even when the learner has access to many. Requiring every example to state every Boolean variable would make the learning cost depend on the entire available universe. A positive partial vector can instead name only enough facts to guarantee the concept. The learner’s cost may then track variables that actually appear in natural examples rather than every proposition that could have been mentioned.

This economy comes with unusually strong semantics. In contemporary data analysis, an unknown feature often means that its value was not measured. Valiant’s star does not merely report ignorance. If F(v)=1, the determined coordinates constitute a sufficient condition: no legal completion can overturn the positive answer. This lets an oracle test whether a coordinate is necessary by turning it into a star. It also explains why unrestricted DNF later becomes troublesome. Deciding whether all completions satisfy a DNF reaches a tautology problem, so a compact formula need not make the concept query cheap.

The arbitrary distribution D is equally deliberate. Valiant does not assume independent variables, uniform inputs or a helpful margin. Nature may concentrate almost all positive mass in a narrow part of the space. The theorem must work for every such fixed D. This distribution-free quantifier is strong within its scope, but the scope includes only positive vectors. A region with no positive probability can remain completely untested. The guarantee says little about its logical structure and nothing about how D might change later.

Finally, the recogniser g belongs to the same program class X in the paper’s definition. This is a proper-learning requirement: the learner must return the specified kind of representation, not an arbitrary circuit that behaves similarly. Later learning theory often separates proper from improper learning because the latter may be computationally easier. Here the representation is not packaging. It determines which structural updates are countable, which evaluations are feasible and which outputs qualify as solutions.

Probability buys evidence

The paper’s proof engine is easier to see in an urn. Suppose an urn contains at most s types of marble. A type covering more than 1/h of the urn has at least a 1/h chance of appearing on each draw. If important types remain unseen, every new draw has a substantial chance of revealing one. There can be at most s such revelations. A sufficiently long run either discovers them or makes the unlucky alternative improbable.

Valiant defines L(h,s) as the smallest number of independent Bernoulli trials needed so that, when each trial succeeds with probability at least 1/h, the chance of seeing fewer than s successes is below 1/h. A Chernoff-style calculation gives the convenient upper bound L(h,s)≤2h(s+ln h). The bound is deliberately loose. Its intellectual job is to prove polynomial dependence when s and h are polynomially bounded, not to set an operational sample budget.

How the combinatorial bound enters the algorithms

The urn story is the proof’s reusable core. In Algorithm A, define a success as deleting at least one clause. If the current g still rejects more than 1/h of the positive mass, an EXAMPLES call lands in that rejected region with probability greater than 1/h. Any such example must delete something, because g rejects precisely when at least one surviving clause is false. The total number of deletion events is bounded by the initial clause count, so the process matches Bernoulli trials with at most s structural successes available.

A subtle point prevents a circular argument. The identity of the missed region changes after each deletion, so the trials are not repeated tests of one fixed event. The lemma needs only a lower bound on the conditional probability of the next success while the bad state persists. Whenever current missed mass exceeds 1/h, the next independent draw from D has that much chance to refute a surviving restriction. Adaptation changes which restriction falls, not the probability logic linking large residual mass to another opportunity.

There are two ways the run can finish. The useful way is that missed mass drops below 1/h. The apparently bad way is that it stays large while fewer than s structural changes occur during all L(h,s) draws. The definition of L makes the second history less likely than 1/h. This converts a deterministic progress measure, the remaining number of possible updates, into a probabilistic stopping guarantee.

The proof therefore does not identify a unique target formula. It certifies predictive coverage relative to D while protecting the one-sided invariant. Many syntactically different conjunctions can accept the same high-mass positive region. Valiant treats that non-identifiability as acceptable because the task is to acquire a recognition program, not reconstruct the teacher’s exact source code. That distinction separates learning a function well on natural inputs from identifying its generating description.

Clauses learn by disappearing

For a fixed integer k, a k-CNF formula is a conjunction of clauses, each containing at most k literals. Valiant’s Algorithm A begins with the conjunction of every possible clause of width up to k over t variables and their negations. This initial recogniser accepts almost nothing. Each positive example deletes every surviving clause that the example fails to make true.

The direction matters. The learner does not add patterns that happen to fit. It removes restrictions refuted by genuine positives. Any clause logically required by the target survives every positive example, so the learned conjunction never accepts a vector that the target rejects. Extraneous clauses may survive for a while and cause false negatives. If those clauses hide more than 1/h of the positive mass, a fresh example has more than 1/h probability of deleting at least one. Since fewer than (2t)^k+1 clauses can be deleted, the combinatorial bound closes the proof.

Theorem A, reconstructed as invariants

The initial formula g contains every clause with at most k literals selected from the 2t signed literals. Some choices are redundant or contradictory, but the crude count is enough: fewer than 2t+(2t)²+…+(2t)^k, which the paper bounds by (2t)^k+1. For fixed k this is polynomial in t. Both initial construction and each pass over the candidates therefore remain polynomial. The theorem would lose its computational content if that set could not be represented and scanned feasibly.

The safety invariant rests on a maximal formula B. Imagine conjoining every width-k clause that is true for every positive vector of f. Since the target itself is a k-CNF, these shared clauses together compute the same total Boolean function as f. No positive example can ever delete a clause in B. The running g always contains B, possibly together with extra clauses. Conjunction grows stricter when it contains more clauses, so every vector accepted by g is accepted by B and therefore by f. This is the algebra beneath the one-sided guarantee.

Progress concerns the extra clauses. If g misses substantial positive mass, a sampled vector from that region violates at least one extra clause and deletes it. No update can damage B. At most the initial candidate count of deletion events can occur, even when one example deletes several clauses at once. The combinatorial proposition then says that a long period of substantial error without enough deletions is unlikely.

Notice what the algorithm never does. It does not estimate coefficients, minimise empirical risk, compare validation scores or search for the target’s shortest equivalent formula. It uses a monotone version-space movement: begin below the target’s positive set and expand only when positive evidence proves a restriction untenable. This geometry explains why false positives are impossible and false negatives are the only approximation debt.

Theorem A also clarifies the role of representation bias. The learner succeeds because a fixed-width CNF target leaves a polynomially enumerable family of local constraints. If the true concept has a compact description in a different language but no small k-CNF, the theorem does not follow it across representations. Learnability is measured relative to how the rule is written and how the learner is allowed to write its answer.

What the oracle contributes

A monotone DNF is a disjunction of conjunctions with no negated variables. Its prime implicants are minimal positive reasons. Algorithm B starts with the constantly false recogniser. When a positive example is not yet covered, the learner tries replacing each determined bit by *. ORACLE says whether every completion remains positive. Dispensable literals are removed until a prime implicant remains, and that term is added to the disjunction.

If the target has degree d, at most d distinct prime implicants can be discovered. Each discovery uses at most t queries, so the query count is at most dt. As long as more than 1/h of positive mass remains uncovered, the next EXAMPLES call has more than 1/h chance of exposing another term. The same discovery-or-thin-tail lemma therefore gives L(h,d) examples.

Three theorems, three kinds of teaching

Theorem B’s prime-implicant procedure reverses the direction of Algorithm A. The CNF learner begins with too many restrictions and removes them. The monotone DNF learner begins with no accepted region and adds minimal sufficient reasons. Both maintain the same safety property: g’s positive set stays inside f’s. Their progress counters differ. Algorithm A can delete only finitely many candidate clauses; Algorithm B can add at most d prime implicants from a target of degree d.

The query step performs controlled counterfactual editing. Starting from a positive partial vector, the learner erases one determined coordinate and asks whether positivity is still forced. A yes answer licenses permanent removal of that literal from the current term. A no answer restores it. After testing all coordinates, every surviving literal is necessary for that implicant. Monotonicity ensures a unique prime DNF representation, preventing ambiguity about the collection the algorithm is discovering.

For unrestricted DNF, negations disturb this clean route. Prime DNFs need not be unique, and asking whether a partial vector forces the formula can be NP-hard. Valiant salvages a result when examples are total and an oracle remains available, but he carefully weakens what has been obtained: the learner may deduce a program for the Boolean function without a feasible method for answering concept queries on partial vectors. A representation can be compact while the semantics needed by the protocol are expensive.

Theorem C moves further. Read-once expressions use each variable once, arranged as an alternating tree of sums and products. Stronger necessity, possibility and structural-relevance oracles let the learner reconstruct that tree exactly with polynomially many calls and no random examples. The result is not a stronger statistical guarantee for the same evidence. It is an exact identification theorem under a richer interrogation language. Changing the teacher-learner interface changes the frontier of learnable concepts.

That observation remains useful whenever supervision is discussed as though it were a single quantity. Demonstrations, binary labels, counterexamples, membership answers and structural explanations are not interchangeable units. Each exposes different facts about the target. Counting them without stating their semantics can make two learning claims look comparable when they solve different information problems.

The PAC name trap

Valiant’s paper is rightly treated as the origin of probably approximately correct learning. Yet reading it through the later textbook definition erases several choices. The original distribution is over positive, possibly partial vectors. The learner can use membership-style queries in two of the three main results. The output must make no false-positive errors, and h ties confidence to tolerated missed mass. Standard PAC usually samples labelled examples from a distribution over the whole instance space, allows two-sided error and separates ε from δ.

This is more than terminological tidying. A May 2026 preprint by Hanneke, Mehrotra, Velegkas and Zampetakis studies Valiant’s original model directly. It reports that, on finite domains, the query-enabled one-sided model is strictly more powerful than its no-query variant yet strictly less inclusive than standard PAC. The paper is provisional current work, not a reason to rewrite 1984. It is a reason to stop pretending that every later formalism was already present in the founding article.

What the later PAC formulation keeps and changes

The enduring inheritance is a quantifier pattern. For every target in a concept class and every permitted distribution, a learner must use polynomial resources and, with high probability over its samples and internal randomness, output a hypothesis with small distributional error. This pattern makes learnability a property open to upper and lower bounds. It rules out conclusions based on one friendly dataset or one convenient target.

Later textbook PAC formulations typically draw labelled instances from the entire domain. Positive and negative errors both contribute to risk, ε states the allowed error and δ the learner’s failure probability, and membership queries are treated as an optional extension rather than a default channel. Hypotheses may also come from a different class. These changes permit a broad connection to statistical capacity and empirical risk, but they alter the exact formal problem.

Occam-style successors show one way that finite evidence can suffice: if a learner efficiently finds a compact hypothesis consistent with the sample, there are not enough such hypotheses for a badly generalising one to survive many independent tests with high probability. VC-dimension theory replaces raw description count with a combinatorial capacity measure. Both developments generalise the concern already visible in Valiant’s bounded structural updates: a class must not be able to fit arbitrary patterns without paying complexity.

Computational lower bounds then separate the existence of a statistically adequate sample from the ability to find a good hypothesis. A class may have controlled capacity while proper hypothesis search encodes an intractable problem. Cryptographic constructions sharpen the same warning from another direction: functions can be easy to evaluate with a key yet resistant to prediction from feasible interaction. The learning contract therefore needs both a sample ledger and a computation ledger.

Clause-elimination laboratory

The laboratory implements the paper’s fixed-width CNF update on a complete three-bit universe. The hidden target is (x₁∨x₂)∧(¬x₁∨x₃). It constructs every clause of width one or two, samples only target-positive assignments from a chosen synthetic distribution and removes clauses falsified by each observation. It then measures missed positive mass and checks that no target-negative assignment has been accepted.

Set samples to zero to see the maximally restrictive initial hypothesis. Increase the count and watch candidate clauses disappear. Under “Rare corner”, one positive assignment receives little mass and may remain rejected longer. A positive result permits the local conclusion that this finite run preserves the one-sided invariant and reports its distribution-relative missed mass. It does not prove the asymptotic theorem, infer an unknown representation class or model noisy labels.

Where learning stops

Three prices accompany the positive results. First, the representation class is part of the theorem. Fixed-width k-CNF is feasible because the candidate clause pool is polynomial when k is constant. Widen the clauses and enumeration can explode. Second, the evidence channel is part of the theorem. Positive examples alone suffice for Theorem A; Theorem B spends oracle calls; Theorem C spends stronger structural queries. Third, the probability distribution is part of the conclusion. Agreement is required on natural inputs carrying most mass, not on every logically possible input.

These choices also prevent an easy slide from concept recognition to intelligence. A polynomial learner for a Boolean class is a result about acquiring a recogniser under a specific protocol. It does not show understanding, agency, consciousness or human-like learning. Valiant’s remarks about teachers, robots and natural inputs are methodological provocations. The theorems establish computational feasibility for restricted propositional classes.

The successor literature generalised one axis at a time. Blumer and colleagues connected compact consistent descriptions to learning through Occam-style bounds, then related distribution-free learnability to Vapnik–Chervonenkis dimension. Pitt and Valiant developed computational limitations showing that sample sufficiency need not make hypothesis search tractable. The modern research programme therefore separates information-theoretic learnability, computational learnability, query complexity, noise tolerance and representational adequacy.

Five limits that survive the positive theorem

Realizability. The primary proofs assume the target belongs to the stated class and examples are correct positives. There is no annotation noise, concept drift or approximation error between the world and the chosen Boolean language. If contradictory examples arrive, Algorithm A can delete target-defining constraints and its invariant no longer has the promised basis.

Independence and stationarity. EXAMPLES calls are independent draws from one D. Correlated batches, feedback loops and temporally moving populations require new analysis. An arbitrary fixed D is a strong quantifier, but “arbitrary” does not mean “changing during the run”.

Natural-input coverage. The learned rule may behave strangely where D puts negligible mass. Valiant presents this as a feature: agreement matters on natural inputs. The price is that counterfactual or safety-critical regions cannot be dismissed solely because yesterday’s distribution rarely visited them. A separate requirement must give those regions weight or query access.

Interface realism. An oracle may stand for a person, database or deduction system. The theorem counts answers and sometimes acknowledges their hidden difficulty. Whether such answers are reliable, affordable or consistently interpreted is outside the proof. Teacher effort is a resource even when the learning algorithm treats it as one call.

Semantic adequacy. A Boolean recogniser can approximate a labelled concept without capturing why the category matters or how it should transfer. The paper intentionally formalises recognition, not explanation. Its framework makes one form of acquisition tractable; it does not reduce all learning to propositional classification.

What the theorem actually earns

Return to the sealed rule. The learner never opens the envelope and may never reproduce the teacher’s formula. What it can earn is narrower and more useful: under the stated sampling process, a polynomially obtained recogniser will, except on a small-probability run, cover nearly all positive mass without extending beyond the target. The guarantee joins an epistemic claim about unseen examples to an algorithmic claim about the work needed to acquire the rule.

The proof is strongest where its assumptions are inspectable. We can name the target class, enumerate or bound the available structural moves, define exactly what a positive example means, and charge each call. We can point to the invariant that blocks false positives and the progress measure that forces coverage. This inspectability is why the result survives beyond its particular Boolean syntax as a model of how to formulate learnability.

The theorem is weaker where a practical reader may most want comfort. It does not estimate whether a real phenomenon belongs to k-CNF, whether labels are reliable, whether today’s D will persist, or whether the one-sided direction matches the cost of error. It does not select h for a decision-maker. Those are modelling and value choices that must be supplied before the mathematics can attach to a case.

One-sidedness itself can be either prudent or perverse. If a positive answer authorises a costly action, forbidding false positives may be sensible, even at the price of temporary under-coverage. If missing a positive is the severe harm, the direction is poorly chosen. Valiant selects one-sided error because his classes admit it, not because every recognition task should prefer it. A later application must justify which mistakes receive zero tolerance.

The final contribution is a style of boundary drawing. A claim about “learning from examples” should be rejected as incomplete until the example generator, query privileges, hypothesis language, resource scale, loss measure, confidence and deployment distribution are visible. Once those clauses are explicit, disagreement becomes technical: one can weaken an oracle, enlarge a class, add noise, shift D or demand a lower error, then trace exactly which proof step fails.

Memory studio

Teach-back test. Without using “PAC”, “generalisation” or “machine learning”, explain why a learner needs a restricted evidence channel, why its remaining mistakes must be weighted, and why a short list of possible hypothesis changes turns repeated observations into a confidence statement.

Place in the canon

Paper 0010 remains in Stage S0, module S0M1, but it changes the question. The first nine papers establish limits of computation, measures of information, universal induction, program-size complexity and verification cost. Valiant asks which recognition programs can be acquired from incomplete evidence with feasible resources. Cook supplies the polynomial feasibility language and the hardness boundary. Shannon supplies the discipline of probability-weighted uncertainty. Solomonoff supplies the ambition to formalise induction. Valiant binds those ingredients to explicit learning protocols.

The strongest successor branch develops capacity measures, Occam bounds, query learning, noise models and computational learning theory. The strongest critical branch shows that information may be sufficient while computation remains prohibitive. The 2026 re-analysis adds a historiographic correction by treating Valiant’s precise positive-only, query-enabled model as a research object rather than silently replacing it with standard PAC.

Read in sequence, the paper also changes the meaning of feasibility established by Cook. A recognition program may run quickly once known, yet acquiring it can remain hard. Conversely, an adequate approximation may be learnable without recovering the exact rule on every possible input. Computation, verification, description and acquisition now form distinct resource questions. That separation prepares the canon to discuss adaptive systems without treating observed competence as evidence that the hidden concept, training path or future behaviour has been fully identified.

The paper therefore supplies a vocabulary for disciplined uncertainty. A learner may be probably reliable without being exactly right, computationally feasible without being universally expressive, and successful on natural inputs without settling remote counterfactuals. Each qualifier narrows the conclusion, but together they make the conclusion provable.

The durable lesson is methodological. “Can this be learned?” is incomplete. Ask from which observations, with which queries, in what representation, under which distribution, to what error, at what confidence and within what computation. Valiant’s achievement was to make those missing clauses visible enough to prove something.