Manuscript Psy04-B@1 · Psy04-B-v1.tex · theorem · 62c2b6f0

Theorem: Exact batch cut optimum

Finite capacity and certified optimization · lines 2258–2289 · proof included or linked

Psy04-B@1#thm:covering, Psy04-B@1#eq:covering

For unrestricted batch encoding through the complete $K$ -state cut,

Q_{C} (n, K) = 1 - \frac{1}{n 2 ^{n}} C \subseteq {0, 1}^{n} 1 \leq ∣ C ∣ \leq K min x \in {0, 1}^{n} \sum c \in C min d_{H} (x, c) .

For a more restricted streaming architecture this expression remains an upper bound; attainment is not automatic.

Proof. The deterministic-table reduction remains valid. Each memory value specifies an $n$ -bit answer word. Input $x$ encoded as $m$ has score

1 - \frac{1}{n} d_{H} (x, c_{m}) .

For fixed answer words, nearest-word batch encoding is optimal. Optimize and average over the input words.

A restricted streaming encoder is a subset of the batch class and cannot exceed its optimum.

Displayed formulas in this passage

Psy04-B@1#eq:covering · line 2262
$Q_{C} (n, K) = 1 - \frac{1}{n 2 ^{n}} C \subseteq {0, 1}^{n} 1 \leq ∣ C ∣ \leq K min x \in {0, 1}^{n} \sum c \in C min d_{H} (x, c) .$
unlabeled · line 2280
$1 - \frac{1}{n} d_{H} (x, c_{m}) .$