State Compression and When It Is Worth It
What This Concept Is
Several different operations are called state compression. Keep them distinct:
| Operation | What it changes | Required argument |
|---|---|---|
| Encode a subset as bits | Representation | Encoding is exact for the declared universe |
| Merge equivalent histories | Number of states | Future choices and contributions are preserved |
| Discard dominated states | Retained alternatives | Every continuation remains achievable at no worse objective |
| Roll old layers | Live storage | No future reader needs the discarded layer |
These operations do not automatically reduce time by the same factor as memory. A compact integer key can still name exponentially many distinct states.
Why It Matters Here
This prevents an optimization from quietly changing the mathematical problem. It also connects proof to engineering: an input bound of "small n" is not a memory budget, and a state count says little without representation and transition costs.
Concrete Examples
Dominance for knapsack frontiers. After the same item prefix, partial selection A with weight no greater than B's and value no less than B's dominates B for at-most-capacity maximization. Both have the same remaining items, so any continuation of B also fits after A with no lower value. Dominance can discard B when finding one optimum. It may discard distinct optimal selections needed for counting, or fail under exact-fill requirements. Frontier size may still be exponential in the worst case.
Narrow-grid dominoes. Process a board column by column. A mask identifies cells in the current column already occupied by horizontal dominoes from the previous column. Fill remaining cells with vertical dominoes within the column or horizontal dominoes into the next. The outgoing mask records only the latter. Start with mask 0 and accept only final mask 0. On a height-1 board there is one tiling for even width and none for odd width. For height 2, widths 0,1,2,3 give counts 1,1,2,3. Do not assume O(width*2^height) time without counting how many outgoing masks are generated per incoming mask.
Memory arithmetic. A rectangular TSP table for n=20 has 20*2^20 slots. At eight bytes per slot it takes 160 MiB before parents and runtime overhead. That is a lower-level representation estimate, not a promise for a Python dict. Measuring shallow container size alone omits referenced keys and integers.
Common Confusion / Misconceptions
Hashing states is not a correctness-preserving compression if collisions are treated as equality. Ordinary dictionaries compare keys after hashing; a truncated fingerprint used alone needs a probabilistic contract. Run-length encoding only helps if order and transition behavior are preserved. Rolling layers does not repair missing historical constraints or erase output costs.
How To Use It
First keep a clear full-state specification. Name the exact transformation and prove its invariant. State which outputs survive: a value, one witness, or all witnesses. Estimate worst-case states, transitions, live bytes and answer bits. Then measure on representative reachable densities with recorded environment and input sizes. Retain tiny exhaustive comparisons as regression checks.
Check Yourself
Why does weight/value dominance require the same processed item prefix? Which compression can invalidate counting while preserving one optimum? Why does a 2^h profile count not establish a 2^h transition count?
Mini Drill or Application
After one item prefix, alternatives are (weight,value)=(2,5),(3,4),(4,7).
Feedback: (3,4) is dominated by (2,5) for at-most optimization;
neither of the others dominates the other. Explain why exact final weight 3
with no remaining items invalidates that pruning rule.
Read This Only If Stuck
Skiena: state-space limitations. Use state and resource contracts to separate semantic reduction, memory layout and measured limits.