NIST

British Museum technique

(algorithmic technique)

Definition: Find a solution by checking all possibilities one by one, beginning with the smallest. This is a conceptual, not a practical, technique where the number of possibilities are enormous.

Generalization (I am a kind of ...)
exhaustive search, breadth-first search.

See also brute force.

Note: For instance, one may, in theory, find the smallest program that solves a particular problem in the following way: Generate all possible source codes of length one character. Check each one to see if it solves the problems. (Note: the halting problem makes this check troublesome.) If not, generate and check all programs of two characters, three characters, etc. Conceptually this finds the smallest program, but in practice it takes far more time than the age of the universe.

Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. is possible or impossible.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 12 January 2005.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "British Museum technique", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 January 2005. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/britishMuseum.html