Моделирование на забывающих RAM-машинах
Для каждой приемлемой модели вычислений существует преобразование независимых машин в эквивалентные забывающие машины (т.е., в забывающие машины, вычисляющие ту же самую функцию) [GO,O]. Вопрос заключается в ресурсозатратах для этих преобразований, а именно в определении времени замедления работы забывающей машины. Например, машина Тьюринга с одной лентой может моделироваться посредством забывающей машины Тьюринга с двумя лентами с логарифмическим замедлением времени выполнения. Ниже исследуется подобный процесс, но для модели вычислений с произвольным доступом к памяти (RAM-машины). Основное достоинство RAM-машины – это способность мгновенно получать доступ к произвольным ячейкам памяти. В контексте настоящей работы, приводится следующий основной неформальный результат для RAM-машины [GO,O].
Пусть RAM(m) означает RAM-машину с m ячейками памяти и доступом к случайному оракулу [ГДж]. Тогда t шагов независимой RAM(m)-программы может моделироваться менее чем за O(t(log2 t)3) шагов на забывающей RAM(m(log2 m)2).
Таким образом, можно увидеть, как провести моделирование независимой RAM-программы на забывающей RAM-машине с полилогарифмическим увеличением размера памяти и полилогарифмическим замедлением времени выполнения. В то же время, простой комбинаторный аргумент показывает, что любое забывающее моделирование независимой RAM-машины должно иметь среднее число W(lоg t) затрат. В связи с эти приводится следующий аргумент.
Пусть машина RAM(m) определена как показано выше. Тогда каждое забывающее моделирование RAM(m)-машины должно содержать не менее max{m,(t-1)log m} операций доступа к памяти при моделировании t шагов оригинальной программы.
Далее рассмотрим сценария наихудшего случая, при котором противник активно пытается получить информацию, вмешиваясь в процесс вычислений. Неформально говоря, моделирование RAM-машины на забывающей RAM-машине является доказуемо защищенным от вмешательства,
если моделирование остается забывающим (т.е.
не вскрывает какой-либо информации о входе за исключением его длины) даже в случае, когда независимый «мощный» противник исследует и изменяет содержимое ячеек памяти. В связи с этим приводится следующий аргумент.
В условиях определения RAM(m)-машины t шагов независимой RAM(m)-программы могут быть промоделированы (доказуемо защищенным от вмешательства способом) менее чем за O(t(log2t)3) шагов на забывающей машине RAM(m(log2m)2).
Необходимо отметить, что вышеприведенные результаты относятся к RAM-машинам с доступом к случайному оракулу. Чтобы получить результаты для более реалистичных моделей вероятностных RAM-машин, необходимо заменить случайный оракул, используемый выше, псевдослучайной функцией. Такие функции существуют в предположении существования односторонних функций с использованием короткого действительно случайно выбранного начального значения (см., например, [Ва1]).
