Неуязвимые генераторы определяются следующим образом:
Пусть - отношение NP, а - машина, которая принимает . Неформально программа является неуязвимым генератором, если на входе она создает пары свидетельства экземпляра , где , согласно распределению, при котором любой противник за полиномиальное время, которому дано не может найти свидетельства того, что с заметной вероятностью для бесконечно большого числа длин .
Неуязвимые генераторы, впервые определенные Abadi et al. нашел много приложений в криптографии.
Существование неуязвимых генераторов основано на предположении, что , однако этого, возможно, недостаточно (см. Также смежную тему ).
Теорема 3 Абади и соавт. В статье, приведенной выше, показано, что любое доказательство существования неуязвимых генераторов не релятивизируется:
Теорема 3. Существует оракул такой, что , и неуязвимые генераторы не существуют относительно B.
Я не понимаю часть доказательства этой теоремы. Пусть обозначает непересекающуюся операцию объединения . Пусть - PSPACE-полный язык выполнимых количественных булевых формул, а - чрезвычайно разреженный набор строк максимальной колмогоровской сложности. В частности, содержит одну строку каждой длины , где последовательность определяется следующим образом: , является трижды экспоненциальной по , для; еслии, тоимеет колмогоровскую сложность.
В статье говорится , что по отношению к , то справедливо , что . Вы можете объяснить? (Также, пожалуйста, уточните, является ли рекурсивным.)