go-v.orgcodex
Menu
Page tools

codex · Philosophy

Compression theorem

In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions. The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions.

Wikipedia contributors, "Compression theorem", Wikipedia, revision 1258125946, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex