Теорема о прямом произведении, неофициально, говорит, что вычисление экземпляров функции f сложнее, чем вычисление f один раз.
Типичные теоремы о прямом произведении (например, лемма Яо XOR) рассматривают сложность среднего случая и утверждают (очень грубо), что не может быть вычислено схемами размера s с вероятностью лучше p , тогда k копий f не может быть вычислено схемы размером s ′ < s с вероятностью лучше, чем p k .
Я ищу различные типы теорем о прямом произведении (если они известны). В частности:
(1) Скажем, мы фиксируем вероятность ошибки и вместо этого интересуемся размером схемы, необходимой для вычисления k копий f ? Есть ли результат, который говорит, что, если f не может быть вычислено схемами размера s с вероятностью лучше, чем p , то k копий f не может быть вычислено с вероятностью лучше, чем p, используя схему размером меньше O ( k ⋅ s ) ?
(2) Что известно в отношении сложности наихудшего случая ? Например, если не может быть вычислено (с ошибкой 0) схемами размера s , что мы можем сказать о сложности вычисления k копий f (с ошибкой 0)?
Любые ссылки будут оценены.
Просто чтобы дополнить ответ Ора, были изучены вопросы вида (1) [сколько ресурсов требуется, чтобы преуспеть в k копиях], и соответствующие теоремы называются «теоремами прямой суммы». Как и в случае теорем о прямом произведении, теоремы о прямой сумме могут выполняться или не выполняться в зависимости от установки.
источник