Теорема Сэвиджа связывает временную сложность вычисления на детерминированной машине Тьюринга со сложностью схемы из функциональных элементов. Если фиксированная машина \(M\) на каждом слове длины \(n\) завершает вычисление не более чем за \(T_M(n)\) тактов, то вычисляемую ею на входах длины \(n\) функцию можно реализовать СФЭ сложности \(O(T_M(n)^2)\)
Доказательство строит схемную развёртку вычисления по времени и позициям ленты. Более точно, если за \(T\) тактов используется \(s\) ячеек ленты, достаточно таблицы размера \(T\times s\) и схемы размера \(O(sT)\); для одноленточной машины \(s=O(T)\), откуда получается \(O(T^2)\). Поэтому полиномиальное время машины Тьюринга влечёт полиномиальный размер соответствующего семейства схем, хотя обратное утверждение из этой теоремы не следует.
Что важно запомнить
- Время \(T_M(n)\) измеряет число тактов машины на входах длины \(n\).
- Теорема Сэвиджа даёт схемную реализацию размера
- Квадрат возникает из пространственно-временной таблицы порядка \(T\times T\).
- Локальное правило перехода машины моделируется схемным элементом постоянной сложности.
- Теорема устанавливает направление «машина Тьюринга → схема» и сама по себе не является обратным моделированием.
Формулировка теоремы
Рассмотрим фиксированную детерминированную машину Тьюринга \(M\). Обозначим через \(T_M(n)\) максимальное время её работы на словах длины \(n\). Теорема Дж. Сэвиджа утверждает: для каждого \(n\) вычисление можно смоделировать схемой из функциональных элементов, причём \(L(\Sigma_n)=O(T_M(n)^2)\)
Машина \(M\) и конечный базис функциональных элементов фиксированы. Поэтому константа, скрытая в \(O(\cdot)\), не зависит от \(n\).
Идея схемного моделирования
Вычисление машины представляют последовательностью конфигураций. Обозначим через \(s\) число ячеек ленты, фактически затронутых за \(T\) тактов. Тогда достаточно рассмотреть пространственно-временную таблицу размера порядка \(T\times s\): одна координата задаёт момент времени, другая — позицию ленты.
Содержимое каждой ячейки следующей строки определяется только ограниченной окрестностью предыдущей строки и текущим состоянием машины. Такое локальное преобразование реализуется элементом постоянной сложности. В конструкции получается порядка \(Ts\) локальных блоков, то есть размер \(O(sT)\). Для одноленточной машины \(s=O(T)\), поэтому получаем используемую в курсе оценку \(O(T^2)\). Двоичное кодирование символов и состояний меняет размер только в постоянное число
Смысл результата
Если \(T_M(n)=O(n^k)\), то для каждого размера входа существует схема размера \(O(n^{2k})\). Это неравномерное моделирование: для каждого \(n\) строится своя схема \(\Sigma_n\).
Теорема даёт верхнюю оценку схемной сложности через время конкретного машинного вычисления. Из неё нельзя без дополнительных условий вывести обратную оценку времени по размеру произвольной схемы.
Пример простыми словами
Если алгоритм на фиксированной машине Тьюринга обрабатывает вход длины \(n\) за \(T_M(n)=O(n^3)\) тактов, теорема Сэвиджа гарантирует семейство СФЭ размера не более \(O(n^6)\). Это верхняя оценка, а не утверждение, что минимальная схема обязательно имеет порядок \(n^6\).
Частые ошибки
- Менять направление теоремы и утверждать, что схема размера \(L\) автоматически даёт машину Тьюринга времени \(O(\sqrt{L})\).
- Понимать \(O(T^2)\) как точное равенство или как оценку минимальной схемы. Это конструктивная верхняя граница.
- Забывать неравномерность модели: схема строится отдельно для каждого фиксированного размера входа \(n\).
