ProLT · Lecture E4 · 37 of 37
Designing observations for a purpose
In this lecture
Complete transcript
Show transcript
The manuscript suggests designing observations for a purpose as further work. This extension gives a small, explicitly stipulated example. We will not claim a new algorithm, complexity classification or real-world cost model from this four-state calculation.
Our original cards use X for dot and Y for stripe: A has only a dot, B both, C only a stripe, and D neither. Their two-bit annotations follow X,Y order. A selected signature lists answers to the chosen test slots. Positive combinations of test regions generate the opens. Choosing a test makes it available; it does not assert its answer. Two states are distinguished here when those selected signatures differ.
One goal is to distinguish designated valuations by different signatures. Another is to make a target subset open so membership can be certified. These goals need not select the same tests, even on the same carrier.
Allow only three candidate tests: X, Y and their conjunction. Assign acquisition costs one, three and two respectively. These invented planning costs are separate from the coordinate weights used in the distance lectures.
With three candidates there are only eight menus to inspect. Exhaustive enumeration solves this tiny example. It does not prove that a particular procedure scales well or is optimal for a general observation-design problem.
X differs at A and D, while Y is false at both and the conjunction is false at both. The single X test therefore distinguishes the pair. Its cost is one, the least positive cost in the declared library.
Selecting that test changes the menu. It does not assert that X is true and does not remove D. The design objective concerns potential distinctions supported by the interface, not a premise update already performed.
Now seek a menu making the singleton B certifiable. X alone cannot do this because its true region also contains A. Y alone also includes C. Distinguishing one designated pair was therefore not the same design task.
The conjunction's truth region is exactly B. Selecting it alone makes B open at cost two. Selecting X and Y separately also generates B through intersection, but their total acquisition cost in our toy library is four.
For a signature map, injective means that different input states always give different output signatures.
To distinguish every valuation, the signature map must be injective. X and Y together achieve this at total cost four. The conjunction alone has only true and false signatures and cannot separate three of the false valuations.
The other two-test menus still merge a pair. X with the conjunction cannot distinguish C from D. Y with the conjunction cannot distinguish A from D. Thus, within our declared library, X and Y is the least-cost menu giving full separation. Adding the conjunction raises cost without adding a needed distinction.
In the stipulated library, compare the cheapest way to make B alone open with the cheapest way to distinguish every valuation. Why is the cheaper event-certification menu insufficient for the stronger separation goal?
The conjunction alone certifies B for cost two, but A, C and D share its false signature. X and Y together cost four and distinguish all points. The optimal answer depends on the objective and the allowed test library.
A useful design problem states exactly what must be distinguished or certified, which formulas may be selected and which costs are being minimized. An exhaustive toy example illustrates that formulation; it does not establish the further algorithmic or complexity results proposed by the manuscript.

