В теории сложности вычислений , то теорема сжатия является важной теоремой о сложности из вычислимых функций .
Теорема утверждает, что не существует класса наибольшей сложности с вычислимой границей, который содержит все вычислимые функции.
Теорема сжатия
Учитывая гёделевскую нумерацию вычислимых функций и меры сложности Блюма где класс сложности для граничной функции определяется как
Тогда существует полная вычислимая функция так что для всех
а также
Рекомендации
- Саломаа, Арто (1985), "Теорема 6.9", Вычисления и автоматы , Энциклопедия математики и ее приложений, 25 , Cambridge University Press, стр. 149–150, ISBN 9780521302456.
- Зиманд, Мариус (2004), «Теорема 2.4.3 (теорема о сжатии)», Вычислительная сложность: количественная перспектива , North-Holland Mathematics Studies, 196 , Elsevier, p. 42, ISBN 9780444828415.