Модели доступа
Необходимо начать с определения модели доступа как последовательности ячеек памяти, к которым ЦП обращается в процессе вычислений. Это определение распространяется также на оракульный ЦП.
Определение5.7. Модель доступа, обозначаемая как Аk(y), детерминированной RAMk-машины
на входе y – это последовательность (a1,...,ai,...) такая, что для каждого i, i-тое сообщение, посланное машиной CPUk
при ее взаимодействии с машиной MEMk(y), имеет форму (·,ai,·).
При рассмотрении вероятностных RAM-машин, мы определяем случайную величину, которая для каждой возможной функции f принимает модель доступа, соответствующая вычислениям, в которых RAM-машина имеет доступ к этой функции. В связи с этим дается следующее определение.
Определение 5.8. Модель доступа, обозначаемая как
– это случайная величина, которая принимает значение модели доступа машины RAMk на некотором входе y и при доступе к однородно выбранной функции f.
Теперь можно перейти к определению забывающей RAM-машины. Мы определяем забывающую RAM-машину как вероятностную RAM-машину, для которой распределение вероятностей последовательности адресов памяти, к которым осуществляется доступ в процессе выполнения программы, зависит только от времени выполнения и не зависит от конкретного частного входа.
Определение 5.9. Для каждого kÎN определим забывающую RAMk-машину
как вероятностную RAMk-машину, удовлетворяющую следующему условию. Для каждых двух строк y1 и y2, если ½
Интуитивно, последовательность операций доступа к памяти забывающей RAMk-машины не открывает никакой информации относительно входа за исключением значения времени выполнения на этом входе.
Определения RAM-машины и забывающей RAM-машины необходимо для того, чтобы дать точное определение забывающего моделирования
независимой RAM-машины посредством забывающей RAM-машины.
Определение моделирования в данном случае минимально необходимое, - требуется только, чтобы обе машины вычисляли одну и ту же функцию. Кроме того, необходимо потребовать, чтобы входы, имеющие идентичное время выполнения на оригинальной RAM-машине, сохраняли бы идентичное время выполнения на забывающей RAM-машине. Для простоты, ниже представляется только определение для забывающего моделирования детерминированных RAM-машин.
Определение 5.10. Для данных машин, - вероятностной RAM'k', и RAMk вероятностная машина RAM'k' моделирует забывающим образом RAMk, если выполняются следующие условия:
вероятностная машина RAM'k'
моделирует RAMk с вероятностью 1. Другими словами, для каждого входа y и каждого выбора оракульной функции f выход оракула RAM'k' на входе y и при доступе к оракулу f равняется выходу RAMk на входе y;
вероятностная машина RAM'k'
– является забывающей. Необходимо подчеркнуть, что здесь рассматривается модель доступа RAM'k' на фиксированном входе и случайно выбранной оракульной функции.
Случайная величина, представляющая собой время выполнения вероятностной RAM'k' на входе y полностью определена текущим временем RAMk на входе y.
Следовательно, модель доступа при забывающем моделировании (которая описывается случайной величиной, определенной над выбором случайного оракула) имеет распределение, зависящее только от времени выполнения оригинальной машины. А именно, пусть
на этих входах (т.е., y1
и y2) идентично.
Теперь мы обратимся к определению затрат при забывающем моделировании.
Определение 5.11. Для данных вероятностных машин RAM'k'
и RAMk предположим, что вероятностная RAM'k'
моделирует забывающим образом вычисления RAMk
и путь g:N®N - есть некоторая целочисленная функция. Тогда затраты на моделирование являются не больше g, если для каждого y требуемое время выполнения RAM'k' на входе y ограничено сверху g(T)T, где T
обозначает время выполнения RAMk
на входе y.
