Sheep-Counting Problems

If you ask me:

What are you thinking about?

and I answer:

Birds.

then this is one of those cases where the answer is easier to give than to justify.

But I could say that I was thinking about math, and then hand you a page of arithmetic problems where I filled in the answers. You still would not have seen what happened in my head, but you could have an idea.

I think there is an interesting family of problems here: when can a person prove, or at least give useful evidence for, what they were thinking about?

I call these sheep-counting problems.

Arithmetic

I imagine being given a sheet like this:

137 × 284 = ______
519 - 287 = ______
84 × 63 = ______
...

A few minutes later, I can return it like this:

137 × 284 = 38,908
519 - 287 = 232
84 × 63 = 5,292
...

Given that the sheet was fresh, I returned it promptly, and I had no outside help, there should not be much doubt that I was thinking about math for a while.

This gives a useful baseline: the exercises can be chosen fresh, the amount of work can be increased by adding more of them, and the answers are easy to verify. Later examples lose one or more of these conveniences.

Counting sheep

You could ask me:

Count sheep in your head for ten minutes.

The task can begin and end entirely in my head. Nothing needs to be said or written down afterward.

Yet if I start yawning and fall asleep, that is some evidence that the sheep were there.

The sleeping guard

A guard watches a building through the night. On a quiet night, a good guard may do almost nothing. The job still requires staying alert enough to notice an intruder, an alarm, a door opening, or anything else that should be reported.

The shift ends and nothing happened. That fits an alert guard, but it also fits a guard who fell asleep five minutes after starting. An event changes the situation: if something happens and the guard notices it and signals, vigilance has had an occasion to become visible.

The problem is the quiet interval. Attention can matter for hours without producing any trace at all.

Chess party

A jealous girlfriend leaves her boyfriend at a party and tells him to play chess while she is away. He plays twenty one-minute games.

When she returns, the games leave a record of many decisions spread across the interval. Every opponent move supplies a fresh position, so the player repeatedly has to react to something that was not known at the start.

The useful feature here is that the evidence is distributed through time because the input is distributed through time. That is different from a worksheet that might have been completed early and then left alone.

The girlfriend's actual reason for choosing chess will matter later.

Puzzles without a challenge

So far, somebody else has supplied the task: exercises, sheep counting, guarding, chess. There is also the case where the prover begins on their own and still wants to leave something checkable afterward.

A party seems like a good place to look because the room already contains public information: people, names, positions, and whatever other structure happens to be there.

A computer-scientist solution

The first construction that came to my mind is very computer-scientist-shaped. A public rule turns every guest's name into an integer, and adding those integers gives a number

\[ N. \]

The prover can factor \(N\) and later present the factors. A verifier only has to multiply them and check that their product is \(N\).

In practice, this might sound like:

What are you thinking about?

I'm factorizing. Alice, Bob and Charlie's names add up to a number whose factorization is 3215031751 × 118670087467 × 307768373641.

From computer science point of view, this is perfect: factorization is difficult, while checking a proposed factorization is straightforward.

But large-integer arithmetic is cumbersome to do mentally, and even checking the product of large factors may be expensive for a person. The construction has the right asymmetry and the wrong human scale.

Six objects, including the empty spot

A spatial version is much easier to state. With ten people standing so that no three are exactly in a line, there are always five whose convex hull contains no other guest. In less geometric language, five people surround a patch of the room with nobody else standing inside it.

Harborth's empty-pentagon theorem guarantees that such a set of five exists. The witness is only the five people; their positions show whether anyone else lies inside the pentagon.

This is much closer to the kind of mental task I want. The input is already in front of the prover, the answer is small, and verification is visual. What I do not know is how difficult the search is for a person who knows the trick.

A monotone subsequence of friends

Another guaranteed puzzle replaces geometry with two orders. Ten people have one public total order, perhaps the order in which they are standing. Their names give another, alphabetical order. Reading the alphabetical ranks in the first order gives a permutation of ten numbers.

Among those ten people there are always four, preserving the first order, whose names are alphabetically increasing or alphabetically decreasing. The Erdős-Szekeres monotone subsequence theorem gives the general guarantee: every sequence of

\[ (r-1)(s-1)+1 \]

distinct values contains an increasing subsequence of length \(r\) or a decreasing subsequence of length \(s\). With \(r=s=4\),

\[ (4-1)^2+1=10. \]

The witness is just four friends. Checking the two orders is easy, while the current ordering can create fresh work even when the prover already knows everybody's name.

This construction adds an extra translation step: the room first has to become two orders. I do not know which search is actually harder once somebody has practiced both. That is an empirical complexity question.

Both party puzzles let the prover start without waiting for a challenge. The environment supplies the instance, and a short public witness survives after the mental search is over.

That freedom creates a possible attack. After seeing the room, the prover can search among several possible problems for one whose answer is already easy. But searching over problems is itself work; preparation, memory, recognition, and search still consume human resources.

What kind of theory is this?

These examples barely look related: arithmetic answers, yawning, a guard's reaction, chess games, a geometric witness. The reason to group them is one common question: can something visible distinguish one hidden cognitive history from another?

So far I have mostly been talking through examples and trying to get a feeling for what these problems have in common. That is useful, but it also makes it easy to rely on intuitions that may be accidents of a particular example. I would like to see how much of this can be made precise. The remainder of this post is therefore an attempt to develop a more formal language for talking about these problems: what is being observed, what hidden processes might produce those observations, and what, if anything, an observation lets us conclude about them. I do not know in advance how much this formalization will explain; even where it fails, I hope it will help separate genuine obstacles from accidents of the examples above.

Sheep counting rules out a certificate-only theory. A yawn is not a proof object, but it can still make one hidden history more plausible than another.

There seem to be two parts to the problem. One is statistical: how different are the visible traces under the two histories? The other is structural: what makes some traces impossible, expensive, or unlikely under one of them?

Evidence and distance

For the moment, suppose the protocol, person-model, and behavioural assumptions are fixed. Later I will say what those contain and where these distributions come from.

Let \(Q\) be a claim about a hidden cognitive history and let \(T\) be the visible trace, taking values in a trace space \(\mathcal T\). The two sides induce trace distributions

\[ P_Q, \qquad P_{\neg Q}. \]

A visible event \(E\) favors \(Q\) when

\[ \Pr(E\mid Q)>\Pr(E\mid\neg Q). \]

The likelihood ratio

\[ L(E)= \frac{\Pr(E\mid Q)}{\Pr(E\mid\neg Q)} \]

measures the strength of that particular observation.

A useful global measure is total-variation distance:

\[ d_{\mathrm{TV}}(P_Q,P_{\neg Q}) = \sup_E \left| P_Q(E)-P_{\neg Q}(E) \right|. \]

It is the largest probability gap obtainable from any event in the trace. That treats the verifier as computationally unlimited.

For a human protocol, the observable separation may be less useful if recognizing the best event is itself difficult. Let \(\mathcal V\) be a class of verifier tests \(v:\mathcal T\to[0,1]\) that the verifier can actually perform, where \(v(t)\) is the probability of accepting trace \(t\). Define the verifier-limited distance

\[ d_{\mathcal V}(P_Q,P_{\neg Q}) = \sup_{v\in\mathcal V} \left| \mathbb E_{P_Q}[v] - \mathbb E_{P_{\neg Q}}[v] \right|. \]

If every test is allowed, this reduces to total variation. If the indicator of a particular event \(E\) is in \(\mathcal V\), then its probability gap lower-bounds \(d_{\mathcal V}\) as well as total variation.

This is the sense in which arithmetic and sleepy sheep can differ in strength while still being the same kind of evidence: their visible traces are distributed differently depending on what happened in the person's head, and some of that difference may be easier to check than the rest.

Distance alone does not explain why the distributions differ. For that, the model needs some account of behaviour and cognitive capacity.

Incentives and strategies

An intruder crosses the yard and the guard does not raise the alarm. Silence may be evidence of inattention, but an attentive guard can deliberately stay silent. Poor chess has the same problem: an attentive player can intentionally play badly. Someone who knows that yawning will be interpreted as evidence can yawn on purpose.

Evidence that survives every deliberate strategy under consideration is strategy-independent. Evidence that works only because some strategies are implausible under the person's incentives is incentive-dependent.

The distinction changes which trace distributions should be compared. A strategy-independent analysis has to admit a much larger false-case strategy class. An incentive-dependent analysis may rule out behaviours that are possible but implausible given what the person wants.

Signal detection theory has a narrower version of this distinction in its separation of sensitivity from response criterion. Here the strategy can depend on arbitrary goals, including cooperating with thieves.

Negative answers

The positive claim

I was solving arithmetic exercises in my head.

can leave completed exercises. Its complement

I was not solving arithmetic exercises in my head.

has a different problem. Somebody who did solve the exercises can often behave afterward exactly like somebody who did not.

If the two histories can generate the same visible behaviour, direct evidence for the negative claim can disappear. An escape needs some trace that becomes unavailable when the unwanted activity happened.

One way to arrange that is to demonstrate another activity that competed for something the unwanted activity would have needed.

Proving something incompatible instead

Suppose the claim is that activity \(B\) did not happen. Evidence for another activity \(A\) can count against \(B\) when the two could not have occurred together:

\[ \text{evidence for }A \quad+\quad A\text{ incompatible with }B \quad\Longrightarrow\quad \text{evidence against }B. \]

This is the role chess was playing for the girlfriend. Chess was not the final fact she cared about. She wanted a positively checkable activity that would leave too little cognitive capacity for some competing activity.

A yes-or-no compatibility relation says that two activities do not fit together, but not why. To construct such incompatibilities rather than merely assume them, I need a quantitative model.

Cognitive flow networks

Take a time interval \(I\) and a directed resource network

\[ N=(G,c), \qquad G=(V,\mathcal E), \]

where each channel \(e\in\mathcal E\) has a time-dependent capacity \(c_e(t)\).

An implementation of an activity assigns load to these channels over time, subject to whatever routing, precedence, release-time, memory, and response constraints define that activity. The same activity can have several implementations that use different parts of the network.

The network is not meant as literal neural wiring. It is a resource model. Channels can stand for whatever bottlenecks turn out to matter: verbal processing, visual attention, working memory, response selection, or something more specific. Wickens' Multiple Resource Theory gives empirical reason to expect interference to depend on which resources tasks share; the network is one mathematical way to express that.

Time is part of the model rather than another scalar resource. In discrete time, the same network can be expanded into layers, one copy for each time step. Processing edges live in or between layers. Holdover edges from one layer to the next can carry state forward and therefore model storage. Fresh inputs, release times, deadlines, and retained information become constraints on which temporal paths are available. This is standard dynamic-flow machinery; time-expanded networks go back to Ford and Fulkerson.

The model may also contain genuinely joint implementations. Two activities need not always consume the sum of their separate costs: one cognitive operation might contribute to both. The saturation result below therefore keeps track of how much bottleneck load a joint implementation may share instead of assuming that separate costs simply add.

If all quantitative information is forgotten and we remember only which sets of activities have some joint feasible implementation, those feasible sets are downward closed: if several activities can coexist, any subset can coexist. Mathematically, that family is an abstract simplicial complex. I only need this as a concise meaning of compatibility. The flow network contains the information about how much capacity is available, where, and when.

Two ways to misjudge a person

The guard gives one kind of mistake. A verifier may believe that an attentive guard always signals an intrusion. If that belief is wrong, the behavioural model is wrong even if the capacity model is perfect.

I have seen another kind. I know somebody who regularly gives a mathematics lecture while writing a manuscript at the same time. Before seeing that, I would have put speaking through a mathematical argument and composing technical prose behind the same bottleneck. For him, that resource model is simply wrong.

The first mistake is about strategy or behaviour. The second is about capacity. A useful person-model has to contain both.

More knowledge can even weaken old evidence. Learning that somebody can yawn on command changes the possible trace distributions for sheep counting. Learning that somebody can route two activities through different cognitive channels can destroy a bottleneck argument that previously looked convincing.

The full person-model

A sheep-counting protocol runs over a time interval \(I\). It specifies how the external input history \(X\) is generated, including any randomness or interventions chosen by the verifier. It also specifies what becomes visible as the trace \(T\), which verifier tests are considered feasible, and a target predicate

\[ Q(X,H) \]

on the hidden cognitive history \(H\).

A person-model \(M\) supplies four things.

First, it contains a dynamic resource network \(N_M\) with capacities over time.

Second, it contains the valid implementations of activities and combinations of activities. These implementation families say what loads, temporal orderings, storage paths, and responses count as actually carrying out the activity. Joint implementations are allowed, so resource sharing between activities can be represented rather than silently double-counted.

Third, it contains a causal strategy class \(\Sigma_M\). A strategy says how the person chooses actions and implementations as the external history is revealed. Together with the protocol's input process, a strategy induces a distribution over possible hidden histories. In particular, it cannot react to a fresh challenge before that challenge arrives.

Fourth, it contains an observation law describing how a hidden history produces a visible trace. This is where ordinary human variability, mistakes, noisy responses, and accidental side effects such as yawning live.

These four pieces describe what can happen, but they do not by themselves say how likely every allowed behaviour is. A Bayesian analysis needs one more ingredient from the verifier: a belief over which person-model and strategy are actually in play. Conditioning that belief on \(Q\) or \(\neg Q\), and then averaging over protocol randomness and the observation law, produces the trace distributions \(P_Q\) and \(P_{\neg Q}\) used earlier.

A strategy-independent analysis asks a different question. It does not average over false-case strategies merely because some look unlikely; a claimed guarantee has to survive every strategy in the class being defended against. The saturation theorem below has exactly this form on each person-model where its assumptions hold.

A sheep-counting problem is the problem of arranging the external input, intervention, and visible trace so that the relevant hidden histories become usefully separated under a defensible model of the person and their behaviour.

Mental effort itself is not the principle. Bounded processing, storage, and temporal availability are mechanisms that can create separation.

Constructing good sheep-counting problems

The full model can express the three resource constructions that appeared earlier.

Proof of work

The factorization, empty-pentagon, and monotone-subsequence puzzles are attempts at human proof of work. A fresh input arrives at some time \(t_0\), and an acceptable response is due by \(t_1\). Any computation that genuinely depends on the fresh input has to fit through processing channels between those times.

Blum and Vempala split the relevant costs into

\[ \operatorname{PREP},\qquad \operatorname{PROC},\qquad \operatorname{VER}. \]

PREP happens before the fresh part of the input arrives. PROC remains afterward. VER is the cost of checking the evidence.

In the flow model, PREP can help only through state that was prepared beforehand, retained through storage edges, and matched to the fresh input later. PROC is the fresh-dependent load that still has to cross processing channels before the deadline. VER determines which trace tests belong to the practical verifier class \(\mathcal V\). A task is useful as proof of work when good performance certifies a substantial lower bound on post-challenge load while an informative verifier remains cheap.

This is an assumption about the task model, not something network notation proves for free. The hard empirical or complexity-theoretic part is obtaining a believable lower bound on how much processing good performance requires.

Proof of space

The same time-expanded network can express proof of space without adding a new resource formalism.

A holdover edge

\[ (v,t)\longrightarrow(v,t+1) \]

represents state surviving from one time layer to the next. Its capacity represents how much state can be retained through that part of the model.

Suppose fresh, unpredictable material is shown at time \(t_0\), disappears, and must be recalled at \(t_1\). If the material cannot be reconstructed from some later source, a valid implementation has to preserve enough information about it across the temporal cuts between \(t_0\) and \(t_1\).

That information requirement matters. Merely pushing arbitrary load through a holdover edge would not prove that anything useful was remembered. The activity model has to connect later recall performance to a lower bound on how much input-dependent state survived the delay. Once such a lower bound is available, successful recall can certify storage load just as successful computation can certify processing load.

A competing memory activity can then be ruled out by the same kind of capacity argument used for work, after crediting any storage work the two activities can genuinely share. The difficult empirical or information-theoretic question is how much retained information a given recall performance actually certifies for this person.

Proof of time

Proof of time uses the temporal coordinate differently. It does not need a large amount of computation or storage. Instead, a claimed state has to be available at many possible times.

A guard who must respond immediately to a probe has to have a response-capable implementation at the layer where that probe arrives. The external input history can contain probe times chosen randomly and hidden until they occur. Because the strategy is causal, the guard cannot move readiness backward in time after seeing the probe.

A non-vigilant strategy may be response-capable on only part of the interval. Hidden random probes sample that temporal coverage. The theorem below turns the covered fraction into a false-pass probability; the resulting trace distribution reveals availability across time rather than accumulated work.

So all three constructions fit the same model, but in different ways:

A long sequential computation gives another possible meaning of proof of time, close to verifiable delay functions in cryptography. In this model I would still classify that mainly as proof of work: its difficulty comes from sequential processing. The random-probe construction is different because its strength comes from coverage of the time axis.

Observation and intervention

Arithmetic exercises, scalable chess, memory challenges, and guard probes all create evidence by changing the situation.

A protocol is observational when it uses evidence that would have arisen anyway and interventional when the verifier introduces exercises, probes, restrictions, or other events that make the hidden state easier to distinguish.

Intervention is not a defect. The constructions above deliberately create fresh demands on parts of the person's model. The complication is that an intervention can also change the property being investigated. Evidence about what happened under the modified situation does not automatically answer a counterfactual question about what would have happened without it.

Theorems

A scalable challenge can prove a negative

The flow model gives a direct way to manufacture negative evidence.

Fix a person-model \(M\), an interval \(I\), and a bottleneck region

\[ D\subseteq \mathcal E_M\times I. \]

Its total capacity is

\[ C_M(D) = \int_I \sum_{e:(e,t)\in D} c^M_e(t)\,dt. \]

For any implementation \(f\), define its load on the same region by

\[ \ell_D(f) = \int_I \sum_{e:(e,t)\in D} f_e(t)\,dt. \]

In discrete time, these integrals are sums.

Let \(B\) be the activity we want to rule out. Its unavoidable individual load on \(D\) is

\[ b_M(B;D) = \inf_{g\in\mathcal F_M(B)} \ell_D(g). \]

Now take a scalable chess-like challenge \(A_\lambda\), where \(\lambda\) controls difficulty. A pass means performance at least \(\tau\). Among individually valid passing implementations, define

\[ w_M(\lambda,\tau;D) = \inf_{f\in\mathcal F_M(A_\lambda,\tau)} \ell_D(f). \]

The infima handle alternative routes through the network. Joint implementations can still reuse some of the same cognitive work. Let

\[ \omega_M(\lambda,\tau,B;D)\ge0 \]

be the least non-negative overlap allowance such that every joint implementation that both passes the challenge and performs \(B\) has load on \(D\) at least

\[ w_M(\lambda,\tau;D) + b_M(B;D) - \omega_M(\lambda,\tau,B;D). \]

An allowance of zero is the fully separable case. A positive allowance says that some bottleneck work may serve both activities and should not be counted twice.

Saturation theorem. If the challenge is feasible by itself and

\[ w_M(\lambda,\tau;D) + b_M(B;D) - \omega_M(\lambda,\tau,B;D) > C_M(D), \]

then passing the challenge and performing \(B\) during the interval are incompatible.

Proof. Every feasible implementation has total load on \(D\) at most \(C_M(D)\). Every joint implementation of a pass and \(B\) has load at least \(w_M+b_M-\omega_M\), which is larger than that capacity. Therefore no such joint implementation exists. \(\square\)

Scalability now has a precise use. If the part of \(B\)'s bottleneck demand that cannot be shared with the challenge is bounded below by some positive margin over sufficiently hard feasible challenges, and the challenge's certified load approaches \(C_M(D)\) from below, then some difficulty eventually satisfies the saturation inequality.

This is what the girlfriend needs from a scalable chess-like game. The game does not have to be intrinsically related to flirting. It has to be tunable until good performance nearly saturates a bottleneck that flirting would also necessarily use, after crediting whatever cognitive work the two activities can genuinely share.

Uncertain person-models turn proof into distance

The girlfriend does not know the person-model exactly. Let

\[ M\sim\pi(\cdot\mid B,K) \]

represent her uncertainty conditional on the hypothesis that \(B\) occurred. If she treats the model as a stable trait independent of \(B\), this is simply her ordinary posterior over models.

For a chosen \(\lambda\) and \(\tau\), let \(G_{\lambda,\tau}\) be the models for which all assumptions of the saturation theorem hold for some relevant bottleneck. Write

\[ \varepsilon_{\lambda,\tau} = \Pr(M\notin G_{\lambda,\tau}\mid B,K). \]

In the ideal capacity model, a pass is impossible together with \(B\) on every model in \(G_{\lambda,\tau}\). Giving every remaining model the maximum possible false-pass probability yields

\[ \Pr(\text{pass}\mid B,K) \le \varepsilon_{\lambda,\tau}. \]

Suppose calibration also gives

\[ \Pr(\text{pass}\mid\neg B,K) \ge \alpha_{\lambda,\tau}. \]

Let \(P_B\) and \(P_{\neg B}\) be the full visible-trace distributions under the two histories. Since pass is one event in that trace,

\[ \boxed{ d_{\mathrm{TV}}(P_B,P_{\neg B}) \ge \alpha_{\lambda,\tau} - \varepsilon_{\lambda,\tau} } \]

whenever the right-hand side is positive. If checking whether the challenge passed belongs to the feasible verifier class \(\mathcal V\), the same lower bound also holds for \(d_{\mathcal V}\).

This is the connection between the resource proof and statistical evidence. The capacity model makes passing impossible on much of the model space; that impossibility forces the two trace laws apart.

The same event gives a likelihood-ratio bound. If \(\varepsilon_{\lambda,\tau}>0\), then a pass favors non-\(B\) over \(B\) by at least

\[ \frac{\Pr(\text{pass}\mid\neg B,K)} {\Pr(\text{pass}\mid B,K)} \ge \frac{\alpha_{\lambda,\tau}} {\varepsilon_{\lambda,\tau}}. \]

If the prior probability of \(B\) was \(p\), Bayes' rule gives

\[ \boxed{ \Pr(B\mid\text{pass},K) \le \frac{p\,\varepsilon_{\lambda,\tau}} {p\,\varepsilon_{\lambda,\tau} +(1-p)\alpha_{\lambda,\tau}} }. \]

A noisy model changes only the false-pass bound. If on the models where the bottleneck argument applies a pass can still occur together with \(B\) with probability at most \(\eta\), then

\[ \beta = (1-\varepsilon_{\lambda,\tau})\eta + \varepsilon_{\lambda,\tau} \]

bounds \(\Pr(\text{pass}\mid B,K)\), so

\[ d_{\mathrm{TV}}(P_B,P_{\neg B}) \ge \alpha_{\lambda,\tau}-\beta. \]

The hardest challenge need not be the best one. Raising \(\lambda\) can make saturation hold on more plausible models, decreasing the false-pass bound, while also lowering ordinary solo performance. The useful difficulty maximizes the resulting separation or likelihood ratio, not raw load.

Recall certifies retained information

The proof-of-space construction has its own quantitative consequence. Let \(Z\) be fresh material drawn from a finite set \(\mathcal Z\), independently of the person's pre-existing state, and assume no later input reveals \(Z\). Let \(S\) be the internal state that survives until recall time. Suppose the later response \(\widehat Z\) is computed from \(S\), with error probability

\[ p_e=\Pr(\widehat Z\ne Z). \]

Fano's inequality gives

\[ H(Z\mid S) \le h_2(p_e) + p_e\log_2(|\mathcal Z|-1), \]

where \(h_2\) is binary entropy. Therefore

\[ \boxed{ I(Z;S) \ge H(Z) - h_2(p_e) - p_e\log_2(|\mathcal Z|-1) }. \]

For uniformly chosen material, \(H(Z)=\log_2|\mathcal Z|\). Good recall therefore forces a lower bound on how much information about the fresh input survived the delay.

In a storage submodel where holdover capacities are measured in information-carrying units, that information has to cross the relevant temporal cuts on holdover paths. If those paths have total information capacity below the bound above, the claimed recall performance is impossible in that person-model. Proof of space is therefore not merely represented by drawing storage edges: recall accuracy can impose a quantitative lower bound on what those edges had to preserve.

Precomputation has a coverage profile

The party puzzles give a finite combinatorial version of the PREP problem. Let \(Y\) range over a finite set of public environmental states and let \(\mathcal T_0\subseteq\mathcal T\) be a finite set of relevant prepared traces. Assume each state has at least one acceptable trace. For each state \(y\), let

\[ A_y\subseteq \mathcal T_0 \]

be the traces accepted for that state.

A prepared trace \(t\) covers the states

\[ B_t=\{y:t\in A_y\}. \]

For a table \(S\subseteq\mathcal T_0\), its covered probability mass is

\[ F(S) = \Pr\!\left[Y\in\bigcup_{t\in S}B_t\right]. \]

If the prover can prepare, remember, recognize, and look up the table \(S\), then a false prover can succeed on at least the states counted by \(F(S)\). The best coverage available from \(k\) prepared traces is

\[ \gamma(k) = \max_{|S|\le k}F(S). \]

The ordinary cover number is

\[ \kappa = \min\{k:\gamma(k)=1\}. \]

The function \(F\) is monotone and submodular. Adding one more prepared response can only help, but the set of new states it covers can only shrink as the table grows.

Human cost is separate. A table with excellent \(\gamma(k)\) may still be unusable if producing, retaining, recognizing, or searching \(k\) responses is too expensive. Those operations are represented by implementations in the full person-model rather than assumed free.

If the challenge distribution itself can be designed, the same incidence structure has a useful dual. The fractional cover number is

\[ \tau^* = \min_{x_t\ge0} \left\{ \sum_t x_t: \sum_{t:\,y\in B_t}x_t\ge1 \text{ for every }y \right\}. \]

Linear-programming duality gives

\[ \tau^* = \max_{z_y\ge0} \left\{ \sum_y z_y: \sum_{y\in B_t}z_y\le1 \text{ for every }t \right\}. \]

Normalize an optimal dual solution by

\[ \mu(y)=\frac{z_y}{\tau^*}. \]

Under this challenge distribution, every single precomputed trace succeeds with probability at most \(1/\tau^*\), and any table of \(k\) traces succeeds with probability at most

\[ \min\!\left(1,\frac{k}{\tau^*}\right) \]

by the union bound.

So the same combinatorics describes both sides: which responses a prover should precompute, and how a verifier should distribute fresh challenges to make small tables ineffective.

This resembles classical time-memory tradeoffs in cryptanalysis, such as Hellman's: expensive precomputation and stored tables can buy cheaper online search. The cover profile here is a different object, built from which prepared human responses cover which environmental states.

A thousand available puzzle families are not a thousand free chances. Searching among them and recognizing an easy one still has a human cost even when the combinatorial coverage is large.

Random probes certify temporal coverage

The proof-of-time construction also becomes a statement inside the full model.

Suppose every allowed false-case strategy commits, before the hidden probe times are drawn, to a response-capable set \(R_\sigma\subseteq I\) satisfying

\[ \frac{|R_\sigma|}{|I|}\le f. \]

If the verifier chooses \(n\) probe times independently and uniformly from \(I\), keeps each probe hidden until it occurs, and accepts only if every probe receives the required immediate response, then every such false-case strategy satisfies

\[ \Pr(\text{pass all }n\text{ probes}) \le f^n. \]

The proof is simply that each independent probe lands in \(R_\sigma\) with probability at most \(f\). Any mixture over strategies chosen before the probes obeys the same bound.

If a genuinely vigilant strategy passes all probes with probability at least \(\alpha\), then the event “pass all probes” also gives

\[ d_{\mathrm{TV}}(P_Q,P_{\neg Q}) \ge \alpha-f^n. \]

The same bound holds for \(d_{\mathcal V}\) whenever checking the probe responses is an allowed verifier test. So proof of time reaches the same statistical output as the saturation construction by a different mechanism. It samples the support of a state over the time axis rather than forcing a large integrated load through one bottleneck.

Repetition can survive an adaptive prover

The previous argument assumes a fixed response-capable set. A more general repetition result allows the person to adapt after every round.

In round \(i\), let \(A_i\) be the event that the verifier accepts that round, and let \(H_{<i}\) contain the complete history visible before it: previous challenges, responses, outcomes, and anything else the strategy can use.

If, after every accepted history \(h_{<i}\), every allowed false-case continuation satisfies

\[ \Pr(A_i\mid H_{<i}=h_{<i},\neg Q,K)\le s_i, \]

then every adaptive false strategy satisfies

\[ \Pr(A_1\cap\cdots\cap A_n\mid\neg Q,K) \le \prod_{i=1}^n s_i. \]

The proof is conditional multiplication. Given that the previous rounds were accepted, the probability of accepting round \(i\) is an average over the possible visible histories, and every term is at most \(s_i\).

Independence is unnecessary. Fatigue, practice, and learning the verifier's strategy matter because they change the later conditional bounds. The random-time guard result is the clean special case with every \(s_i=f\).

Does the theory explain anything?

The framework now has a clearer division of labour. Trace distributions say how much evidence is visible; the verifier class says how much of that separation is practically checkable. The person-model explains where the distributions come from. Dynamic capacity can make some joint histories infeasible; storage edges can force information to persist; random probes can sample temporal coverage.

The saturation theorem is the main constructive result here. Its mathematics is simple; the substantive content lies in establishing defensible lower bounds on task load, capacity, and shared work. Given those, it does more than label two activities incompatible after the fact: it tells a verifier how a scalable challenge can create a negative proof, and under uncertainty it turns that proof into a quantitative lower bound on statistical distance.

Proof of work, proof of space, and proof of time are all expressible, but they are not the same mechanism. Work is throughput, space is retained information, and time is temporal availability. The common output is separation between visible trace distributions. The space result makes the distinction especially sharp: the network supplies storage capacity, while information theory connects successful recall to how much input-dependent state had to survive.

The empirical burden remains large. The network structure, capacities, activity implementations, strategy classes, observation laws, and performance calibration all have to come from assumptions or measurements about real people. If those objects are freely invented, the mathematics can explain anything. The interesting question is whether useful lower bounds and stable structures can actually be learned.

Paradoxes

The formal picture can still produce sound conclusions that miss the broader social question.

Proving that he did not flirt is not proving that he would not flirt

Let \(B\) be flirting during the interval. Suppose the girlfriend chooses a scalable chess challenge for which the saturation theorem applies on much of her posterior over the boyfriend's person-model. Passing can then give strong evidence for the historical claim

\[ \neg B. \]

But the chess instruction is also an intervention: it removes some of the opportunity to flirt. The girlfriend may care about a different predicate. Let \(R\) mean

He would refrain from flirting if he had the opportunity.

If both \(R\) and \(\neg R\) produce the same chess-trace distribution under the intervention, then

\[ d_{\mathrm{TV}}(P_R,P_{\neg R})=0. \]

The same challenge can therefore give strong evidence about what happened during the constrained interval and no evidence at all about what would happen without the constraint.

A stronger guard test can make the guarding worse

Let \(Q\) mean that the guard remains vigilant. A supervisor creates \(n\) test events and records the full response vector

\[ Y^{(n)}=(Y_1,\ldots,Y_n). \]

Suppose the responses are conditionally independent, with

\[ Y_i\mid Q\sim\operatorname{Bernoulli}(a), \qquad Y_i\mid\neg Q\sim\operatorname{Bernoulli}(b), \]

where \(a>b\). More test events make the two response-vector distributions increasingly distinguishable.

But every fake alarm or staged intrusion can also impose a cost on the actual guarding by occupying attention, creating alarm fatigue, or distracting from a real event.

More testing can therefore improve the sheep-counting evidence while making the guard's actual job worse. The statistical ranking and the social ranking move in opposite directions.

Neither paradox is an argument against intervention. They only show that evidence for one predicate under one experiment does not automatically answer a different question.

What I would try next

The scalable-challenge theorem suggests a direct experiment. A chess-like task could be given at several difficulty levels while a second task competes for a suspected shared bottleneck. Solo performance would estimate how often the challenge is passed without the competing activity. Dual-task performance would estimate how much work the two tasks can share and test the saturation assumptions rather than merely assuming them.

The proof-of-space side suggests a similar experiment with fresh material that has to be retained across a delay while a competing memory task varies. The question would be whether later recall supplies a stable lower bound on load through some storage bottleneck.

The random-time guard construction tests the temporal side. Varying the number and timing of hidden probes would show how well they distinguish sustained availability. Mackworth's results already suggest that vigilance changes through a long watch, so timing should matter rather than only the number of probes.

The party puzzles give a different experiment. Repeating the empty-pentagon and monotone-subsequence tasks at nearby sizes could estimate how their post-challenge processing demand changes with problem size, practice, and preparation. The precomputation profile \(\gamma(k)\) could be measured separately by letting participants prepare increasing numbers of answers or puzzle families.

The original question was simple:

What are you thinking about?

A hidden cognitive history can leak into the visible world through answers, side effects, reactions to fresh events, short witnesses, or responses spread across time. Computational hardness is one way to make such evidence difficult to imitate, but it is not the principle underneath all of them.

What is common to all of them is not work. It is separation: something visible is distributed differently depending on what happened in the person's head.

References