Дополнения к базовой модели и вероятностные RAM-машины
Приводимые ниже результаты верны для RAM-машин, которые являются вероятностными в очень строгом смысле. А именно ЦП в этих машинах имеет доступ к случайным оракулам. Однако в предположении существования односторонних функций, случайные оракулы могут быть эффективно реализованы посредством псевдослучайных функций.
Определение 5.2. Для каждого kÎN определим оракульный
CPUk как CPUk с двумя дополнительными лентами, названными оракульными лентами. Одна из этих лент является «только-для-чтения», а другая «только-для-записи». Всякий раз, когда машина входит в специальное состояние вызова оракула, содержимое оракульной ленты «только-для-чтения» изменяется мгновенно (т.е., за единственный шаг) и машина переходит к другому специальному состоянию. Строка, записанная на оракульной ленте «только-для-записи» между двумя вызовами оракула называется запросом, соответствующим последнему вызову. Будем считать, что CPUk имеет доступ к функции f, если делается запрос q и оракул отвечает и изменяет содержимое оракульной ленты «только-для-чтения» на f(q). Вероятностная
машина CPUk – это оракульная машина CPUk с доступом к однородно выбранной функции f:{0,1}O(k) ®{0,1}.
Определение 5.3. Для каждого kÎN определим оракульную RAMk-машину
как RAMk-машину, в которой машина CPUk
заменена на оракульную CPUk. Скажем, что эта RAMk-машина имеет доступ к функции f, если CPUk имеет доступ к функции f и будем обозначать как
