"Записки научных семинаров ПОМИ"
Том 407, стр. 105-110
Полиномиально ограниченный сверху объём изменений программ
на RAM+BOOL для доказательства принадлежности FP
Н. К. Косовский
С.-Петербургский
государственный университет,
Университетский пр. 28,
Петродворец, 198504 Санкт-Петербург, Россия
kosov@nk1022.spb.edu
- Аннотация: RAM+BOOL (т.е. машина прямого доступа
с дополнительными поразрядными логическими операциями) кажется достаточно подходящим математическим понятием алгоритма для того, чтобы более адекватно (относительно операций компьютеров) отразить число шагов вычисления, чем понятие машины Тьюринга. Например, в определении RAM+BOOL имеется косвенная адресация, широко используемая при обработке массивов в компьютере. %Однако за $n$ шагов на RAM+BOOL можно вычислить, например, $2^{2^n}$, что гораздо менее адекватно числу шагов вычисления этой функции на компьютере.
Под использованной памятью (при логарифмическом весе) RAM+BOOL будем понимать максимум по всем шагам вычисления программы на RAM+BOOL сумм длин всех значений содержимых всех использованных ячеек.
В статье для обеспечения принадлежности вычислений на RAM+BOOL
классу \textbf{FP} (т.е. классу алгоритмов, вычислимых
за полиномиальное время на машине Тьюринга) предлагается
использовать введенное автором ранее понятие объёма изменений,
представляющее собой произведение числа шагов вычисления на
длину используемой памяти.
В статье доказан ряд утверждений относительно сложностных
параметров вычислений на RAM+BOOL. Наиболее важным из них
является следующее следствие.
\textbf{Следствие.} \textit{Класс всех программ, написанных
для RAM+BOOL, объём изменений которых ограничен сверху полиномом
от длины записи исходных данных, совпадает с классом \textbf{FP}. }
Библ. -- 5 назв.
- Ключевые слова: RAM, машины Тьюринга, машины Тьюринга с
оракулами-функциями, класс FP
[RAM, Turing macine, function-oracle Turing macine, class FP]
Полный текст(.pdf)