Theorem: Sharp bounded classical-memory exclusion benchmark

For every admitted classical processor with $K\le 2$,

The bound permits arbitrary stochastic encoding, classical delay dynamics, decoding, and input-independent shared randomness.

It is attained by a sequential one-bit implementation.

Proof. By Lemma lem:deterministic, it suffices to consider deterministic tables. For fixed decoder words, the encoder cannot do better than choose a closest word:

There are four inputs and at most two distinct answer words. At least two inputs are not answer words, and each has distance at least one. The distance sum is therefore at least two, giving $Q\le 3/4$.

For attainment, store $X_1$ when it arrives, leave that state unchanged when $X_2$ arrives, and return the stored bit for query 1. For query 2, return a fixed bit or an independent fair guess. The success is