Variantes de teoremas de produtos diretos

11

Um teorema direto do produto, informalmente, diz que computar instâncias de uma função é mais difícil do que computar uma vez.kff

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 .fspkfs<spk

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 ?pkffspkfpO(ks)

(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)?fskf

Todas as referências serão apreciadas.

user686
fonte

Respostas:

10

(1): Esta questão foi estudada no artigo "Rumo a provar fortes teoremas de produtos diretos", de Ronen Shaltiel, e verifica-se que tal conjectura é falsa: por exemplo, pode ser que possa ser computado com probabilidade com tamanho muito menor que , e somente a massa adicional de probabilidade de requer tamanho . Nesse caso, ao computar em instâncias, o circuito pode resolver na maioria das instâncias com tamanho muito menor que e precisará de tamanho apenas em algumas das instâncias.f0.99ps0.01psfkfss

(2): Um teorema do produto direto para a complexidade do pior caso é conhecido para fórmulas e circuitos monótonos, mas é realmente conhecido como falso para circuitos gerais. Para um exemplo fácil, considere uma função que visualiza sua entrada como um vetor e a multiplica por alguma matriz booleana fixa . Então, calcular a função pode exigir tamanho , mas calculá-la em instâncias pode ser feita muito mais rápido que usando um algoritmo de multiplicação de matrizes. Você pode encontrar uma discussão completa sobre esse assunto no livro "A complexidade das funções booleanas", de Ingo Wegener - consulte o capítulo 10.2 aqui:f:{0,1}n{0,1}nn×nfn2nn3http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ .

Ou Meir
fonte
Dei uma olhada no capítulo 10.2 do livro de Wegener (obrigado pela referência!) Que mostra que um resultado de soma direta não pode se manter em geral. Mas há algo conhecido por específico (talvez aqueles com complexidade de circuito menor que )? (Eu ainda estou interessado em pior caso de complexidade, e para circuitos arbitrárias.)f2n
user686
Eu também estaria interessado se algum resultado mais fraco fosse conhecido, por exemplo, quekfs+O(k)
2nkfkf
7

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.

Dana Moshkovitz
fonte