fpf.tools
Library / Computational Thinking DPF
Jump to passage
In this reading
Source · lines 2161–2172

Link to current text

Published source confirmed at last check

Source changed 2026-10-03 11:52:20 UTC · snapshot created 2026-10-03 11:53:41 UTC · last check 2026-10-03 13:05:11 UTC

CMP.11:4.3 - Turn indistinguishability into a resource bound

Use the form that fits the access:

  • Adversary: answer queries while retaining incompatible possible inputs. Show how many queries are needed before no such pair remains.
  • Counting: if each observation has at most b possible replies, q observations have at most b^q transcripts. If N input classes require mutually different outputs, then b^q≥N, giving q≥log_b N for a worst-case depth bound.
  • State or message collision: with fewer than N distinguishable retained states or messages, two of N necessary input classes collide. A shared continuation then forces an error.

Establish that each constructed transcript is consistent with at least one admitted input. An adversary that combines incompatible answers proves nothing about the actual problem. A counting argument needs output-distinct classes, not merely many syntactically different inputs.

When an algorithm already provides an upper bound in the same model, compare the two. Matching orders of growth can establish asymptotic optimality for that model. A gap locates remaining room for a better construction or a stronger argument; it is not itself proof that the current algorithm is improvable.