В теории сложности вычислений аксиомы Блюма — это аксиомы, которые определяют свойства мер сложности на множестве вычислимых функций. Впервые эти аксиомы были сформулированы Мануэлем Блюмом в 1967 году.

Важным является тот факт, что и теорема Блюма об ускорении, и теорема о промежутке верны для любых мер сложности, удовлетворяющих этим аксиомам. Наиболее известными примерами таких мер являются время выполнения (TIME) и объем используемой памяти (SPACE).

Определения

Мера сложности Блюма — это пара , состоящая из гёделевой нумерации вычислимых функций и вычислимой функции

удовлетворяющей следующим аксиомам Блюма. Мы обозначаем через i-ю вычислимую функцию согласно гёделевской нумерации , а через — вычислимую функцию .

• области определения и совпадают.
• множество является разрешимым.