Машина Тьюринга, которой на вход дополнительно подаётся подсказка $a(|x|)$, то есть одинаковая для фиксированной длины входа

Схемная сложность

• По каждой ДМТ, заспознающей язык $L$ за $T(n)$ можно построить семейство распознающих схем размера $O(T^2(n))$ (теорема)
• По каждому семейству схем можно взять машину Тьюринга, которая умеет вычислять схемы, и передать ей схему как подсказку

$SIZE(f(n))$

класс языков, которые распознаются семейством схем размера $f(n)$

$DTIME(T(n)) / a(n)$

Класс языков, которые распознаются ДМТ с подсказкой $a(n)$ за время $T(n)$.