British Museum algorithm

The British Museum algorithm is a general approach to find a solution by checking all possibilities one by one, beginning with the smallest. The term refers to a conceptual, not a practical, technique where the number of possibilities are enormous.

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 problem. (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 tends to take an unacceptable amount of time (more than the lifetime of the universe, in many instances).

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

See also

• Breadth-first search
• Brute-force search
• Exhaustive search
• British Museum

Sources

• Original text by  This article incorporates public domain material from Paul E. Black. "British Museum technique". Dictionary of Algorithms and Data Structures. NIST..