Полиномиально ограниченный сверху объём изменений программ на RAM+BOOL для доказательства принадлежности FP

RAM+BOOL (т.е. машина прямого доступа с дополнительными поразрядными логическими операциями) кажется достаточно подходящим математическим понятием алгоритма для того, чтобы более адекватно (относительно операций компьютеров) отразить число шагов вычисления, чем понятие машины Тьюринга. Например, в определении RAM+BOOL имеется косвенная адресация, широко используемая при обработке массивов в компьютере. Под использованной памятью (при логарифмическом весе) RAM+BOOL будем понимать максимум по всем шагам вычисления программы на RAM+BOOL сумм длин всех значений содержимых всех использованных ячеек.
В статье для обеспечения принадлежности вычислений на RAM+BOOL классу FP (т.е. классу алгоритмов, вычислимых за полиномиальное время на машине Тьюринга) предлагается использовать введенное автором ранее понятие объёма изменений, представляющее собой произведение числа шагов вычисления на длину используемой памяти.
В статье доказан ряд утверждений относительно сложностных параметров вычислений на RAM+BOOL. Наиболее важным из них является следующее следствие.
Следствие. Класс всех программ, написанных для RAM+BOOL, объём изменений которых ограничен сверху полиномом от длины записи исходных данных, совпадает с классом FP.
Библ. – 5 назв.