Um teorema direto do produto, informalmente, diz que computar instâncias de uma função é mais difícil do que computar uma vez.
Teoremas típicos de produtos diretos (por exemplo, o XOR Lemma de Yao) analisam a complexidade de casos médios e argumentam (muito grosseiramente) que não pode ser calculado por circuitos de tamanho com probabilidade melhor que , então cópias de não podem ser computadas por circuitos de tamanho com probabilidade melhor que .
Estou procurando por diferentes tipos de teoremas de produtos diretos (se forem conhecidos). Especificamente:
(1) Digamos que fixamos a probabilidade de erro e estamos interessados no tamanho do circuito necessário para calcular cópias de ? Existe um resultado que diz que se não pode ser calculado por circuitos de tamanho com probabilidade melhor que , cópias de não podem ser calculados com probabilidade melhor que usando um circuito de tamanho menor que ?
(2) O que se sabe sobre a pior complexidade possível? Por exemplo, se não pode ser calculado (com erro 0) por circuitos de tamanho , o que podemos dizer sobre a complexidade da computação cópias de (com erro 0)?
Todas as referências serão apreciadas.
Apenas para complementar a resposta de Or, foram estudadas questões do tipo (1) [quanto de um recurso é necessário para se dar bem em k cópias] e os teoremas correspondentes são chamados de "teoremas de soma direta". Assim como os teoremas diretos do produto, os teoremas de soma direta podem ou não se manter, dependendo da configuração.
fonte