Jump to text
On this page
Copy and source
Published source confirmed at last check

Source changed 2026-11-18 22:51:26 UTC · snapshot created 2026-11-18 22:54:45 UTC · last check 2026-11-18 23:55:20 UTC

CMP.11:2 - Problem

How can one establish a minimum amount of computational work without enumerating every possible algorithm, and use the result without extending it beyond the model that made the proof valid?

An algorithm can make adaptive choices, preprocess data, exploit a promise or use randomization. A proof that ignores an allowed operation can forbid a working procedure. A lower bound valid for a comparison model can disappear when keys have an accessible integer encoding.