Варианты прямых теорем о произведениях

11

Теорема о прямом произведении, неофициально, говорит, что вычисление экземпляров функции f сложнее, чем вычисление f один раз.kff

Типичные теоремы о прямом произведении (например, лемма Яо XOR) рассматривают сложность среднего случая и утверждают (очень грубо), что не может быть вычислено схемами размера s с вероятностью лучше p , тогда k копий f не может быть вычислено схемы размером s < s с вероятностью лучше, чем p k .fspkfs<spk

Я ищу различные типы теорем о прямом произведении (если они известны). В частности:

(1) Скажем, мы фиксируем вероятность ошибки и вместо этого интересуемся размером схемы, необходимой для вычисления k копий f ? Есть ли результат, который говорит, что, если f не может быть вычислено схемами размера s с вероятностью лучше, чем p , то k копий f не может быть вычислено с вероятностью лучше, чем p, используя схему размером меньше O ( k s ) ?pkffspkfpO(ks)

(2) Что известно в отношении сложности наихудшего случая ? Например, если не может быть вычислено (с ошибкой 0) схемами размера s , что мы можем сказать о сложности вычисления k копий f (с ошибкой 0)?fskf

Любые ссылки будут оценены.

user686
источник

Ответы:

10

f0.99ps0.01psfkfss

f:{0,1}n{0,1}nn×nfn2nn3используя алгоритм умножения матриц. Вы можете найти подробное обсуждение этой темы в книге Инго Вегенера «Сложность булевых функций» - см. Главу 10.2 здесь: http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ .

Или меир
источник
f2n
kfs+O(k)
2nkfkf
7

Просто чтобы дополнить ответ Ора, были изучены вопросы вида (1) [сколько ресурсов требуется, чтобы преуспеть в k копиях], и соответствующие теоремы называются «теоремами прямой суммы». Как и в случае теорем о прямом произведении, теоремы о прямой сумме могут выполняться или не выполняться в зависимости от установки.

Дана Мошковиц
источник