Twierdzenie o kompresji

W teorii złożoności obliczeniowej twierdzenie o kompresji jest ważnym twierdzeniem o złożoności funkcji obliczalnych .

Twierdzenie to stwierdza, że ​​nie istnieje największa klasa złożoności z obliczalną granicą, która zawierałaby wszystkie obliczalne funkcje.

Twierdzenie o kompresji

Biorąc pod uwagę numerację Gödela $obliczeniowych$ i miarę złożoności Bluma, gdzie klasa złożoności dla funkcji brzegowej jest zdefiniowana jako $\ varphi }$$\ displaystyle$

${\ Displaystyle \ operatorname {C} (f): = \ {\ varphi _ {i} \ w \ mathbf {R} ^ {(1)} | (\ forall ^ {\ infty} x) \ \ Phi _ {i}(x)\równ.f(x)\}.}$

Wtedy istnieje całkowita obliczalna funkcja, $displaystyle$ że dla wszystkich $i}$

${\ Displaystyle \ operatorname {Dom} (\ varphi _ {i}) = \ operatorname {Dom} (\ varphi _ {f (i)} )}$

I

${\ Displaystyle \ operatorname {C} (\ varphi _ {i}) \ subsetneq \ operatorname {C} (\ varphi _ {f (i)}).}$

•   Salomaa, Arto (1985), „Twierdzenie 6.9”, Obliczenia i automaty , Encyklopedia matematyki i jej zastosowań, tom. 25, Cambridge University Press, s. 149–150, ISBN 9780521302456 .
•   Zimand, Marius (2004), „Twierdzenie 2.4.3 (twierdzenie o kompresji)”, Złożoność obliczeniowa: perspektywa ilościowa , North-Holland Mathematics Studies, tom. 196, Elsevier, s. 42, numer ISBN 9780444828415 .