Compression theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Compression theorem[edit]

Given a Gödel numbering of the computable functions and a Blum complexity measure where a complexity class for a boundary function is defined as

Then there exists a total computable function so that for all

and

References[edit]