Compression theorem

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.

Compression theorem Given a Gödel numbering {style d'affichage varphi } of the computable functions and a Blum complexity measure {style d'affichage Phi } where a complexity class for a boundary function {style d'affichage f} is defined as {style d'affichage mathrm {C} (F):={varphi _{je}en mathbf {R} ^{(1)}|(forall ^{infime }X),Phi _{je}(X)leq f(X)}.} Then there exists a total computable function {style d'affichage f} so that for all {style d'affichage i} {style d'affichage mathrm {Dom} (varphi _{je})= mathrm {Dom} (varphi _{F(je)})} et {style d'affichage mathrm {C} (varphi _{je})subsetneq mathrm {C} (varphi _{F(je)}).} References Salomaa, Arto (1985), "Théorème 6.9", Computation and Automata, Encyclopédie des mathématiques et de ses applications, volume. 25, la presse de l'Universite de Cambridge, pp. 149–150, ISBN 9780521302456. Zimand, Marius (2004), "Théorème 2.4.3 (Compression theorem)", Complexité informatique: A Quantitative Perspective, Études de mathématiques en Hollande du Nord, volume. 196, Elsevier, p. 42, ISBN 9780444828415. P ≟ NP This theoretical computer science–related article is a stub. Vous pouvez aider Wikipédia en l'agrandissant.

Catégories: Computational complexity theoryStructural complexity theoryTheorems in the foundations of mathematicsTheoretical computer science stubs