Sabe-se que existem funções com a seguinte propriedade de soma direta?

15

Essa pergunta pode ser feita tanto na estrutura da complexidade dos circuitos booleanos, quanto na teoria da complexidade algébrica, ou provavelmente em muitas outras configurações. É fácil mostrar, contando argumentos, que existem funções booleanas em N entradas que exigem exponencialmente muitas portas (embora, é claro, não tenhamos nenhum exemplo explícito). Suponha que eu deseje avaliar a mesma função M vezes, para algum número inteiro M, em M conjuntos distintos de entradas, de modo que o número total de entradas seja MN. Ou seja, queremos apenas avaliar para a mesma função a cada vez.ff(x1 1,1 1,...,x1 1,N),f(x2,1 1,...,x2,N),...,f(xM,1 1,...,xM,N)f

A questão é: sabe-se que existe uma sequência de funções (uma função para cada N), de modo que, para qualquer N, para qualquer M, o número total de portas necessárias seja pelo menos igual a M vezes a função exponencial de N? O argumento da contagem simples parece não funcionar, pois queremos que esse resultado seja válido para todos os M. Pode-se chegar a análogos simples dessa questão na teoria da complexidade algébrica e em outras áreas.f

hastings mate
fonte

Respostas:

13

Bem, isso é falso: é possível avaliar M cópias de QUALQUER f usando apenas portas O (N (M + 2 ^ N)) que podem ser muito menores que M * exp (N) (de fato, você é amortizado linearmente). complexidade para M exponencial). Não me lembro de uma referência, mas acho que pode ser algo como o seguinte:

Primeiro adicione 2 ^ N entradas fictícias que são apenas constantes 0 ... 2 ^ N-1 e agora denotam a i-ésima entrada de bits N por xi (assim, para i <= 2 ^ N, temos xi = i, e para 2 ^ N <i <= 2 ^ N + M temos as entradas originais). Agora criamos um trigêmeo para cada uma das entradas M + 2 ^ N: (i, xi, fi) em que fi é f (i) para as primeiras 2 ^ N entradas (uma constante que é conectada no circuito) e fi = "*" de outra forma. Agora, classificamos os trigêmeos (i, xi, fi) de acordo com a chave xi, e deixemos o j-ésimo trigêmeo (i_j, x_j, f_j) a partir disso, calculamos um trigêmeo (i_j, x_j, g_j), deixando g_j ser f_j se f_j não for um "*" e deixe g_j ser g_ (j-1) caso contrário. Agora ordene os novos trigêmeos de volta de acordo com a chave i_j, e você terá as respostas corretas nos lugares corretos.

Noam
fonte
Esperto! Uma coisa menor: temos que classificar os trigêmeos de forma estável (ou em algum outro método que garanta que os trigêmeos com fi≠ “ ” venham mais cedo do que os trigêmeos com fi = “ ”).
Tsuyoshi Ito
Muito esperto e obrigado. Alguma coisa semelhante funciona, no entanto, no cenário de complexidade algébrica, ou não?
amigos estão dizendo sobre matt hastings
11
Eu acho que outra maneira de dizer isso no caso de M ir para o infinito é que você pode investir 2 ^ N * 2 ^ N tempo para criar uma tabela de hash para todos os valores de f, e então você pode calcular todas as cópias em O (N ) Tempo. Acho que há outra razão pela qual pelo menos não devemos saber se algo assim é verdade, mesmo para valores mais brandos de N, que é que daria limites inferiores aos conhecidos. Você seria capaz de construir uma função com limite inferior superlinear pela primeira força bruta para encontrar uma função nas entradas n '= log n (ou talvez n' = loglog n) com grande complexidade e, em seguida, obtendo n / n 'cópias .
Boaz Barak
11
No argumento acima, sobre por que esses resultados levam a limites mais baixos, não sei se o número de repetições é realmente mais moderado, mas também se aplica a campos infinitos.
Boaz Barak
Oi Boaz, De fato, seu comentário é precisamente o motivo pelo qual eu estava interessado na existência dessas funções. No entanto, há um ponto sutil, a "força bruta". Pode ser (que é o que minha pergunta visa), que tais funções existam, mas que não tenhamos um algoritmo que permita demonstrar que uma determinada função possui essa propriedade. Afinal, não parece haver uma maneira de forçar a propriedade que esse limite inferior mantém para todos os M, porque você teria que verificar um número infinito de circuitos diferentes. Portanto, talvez essas funções existam para campos infinitos, mas não podemos mostrá-lo.
Matt Hastings
10

O(2n/n)mmfm2n/n

"Redes que computam funções booleanas para vários valores de entrada"

que isso é falso: contanto que , é possível calcular m instâncias de qualquer f com um circuito do tamanho O ( 2 n / n ) - basicamente o mesmo custo que para m = 1 !m=2o(n/registron)mfO(2n/n)m=1 1

Não consigo encontrar uma cópia não fechada on-line ou uma página inicial para o autor, mas me deparei com o artigo neste processo:

Complexidade da função booleana (série de notas de aula da London Mathematical Society)

Andy Drucker
fonte
Obrigado! Não foi feita uma pergunta sobre paradoxos no TCS? Isso também poderia servir como uma resposta lá :)
Arnab
Obrigado por esta resposta também. Não sendo capaz de ler o processo, acho que, semelhante à resposta anterior, ele pode se basear no número finito de entradas possíveis, novamente a mesma pergunta de acompanhamento acima: e o caso da complexidade algébrica?
amigos estão dizendo sobre matt hastings
Na verdade, parece que Shannon primeiro provou o limite superior de O (2 ^ n / n); Lupanov conseguiu a constante líder certa. Eu corrigi isso. Os detalhes são explicados em "Revendo limites no tamanho do circuito das funções mais difíceis", de Frandsen e Miltersen.
Andy Drucker
5

Em relação à complexidade algébrica, não conheço um exemplo em que a complexidade exponencial se reduz à complexidade amortizada subexponencial, mas pelo menos há um exemplo simples de que a complexidade de M cópias disjuntas pode ser significativamente menor que M vezes a complexidade de uma única cópia :

Para uma matriz "aleatória" n * n A, a complexidade da forma bilinear definida por A (a função f_A (x, y) = xAy, onde xey são 2 vetores de comprimento n) é Omega (n ^ 2 ) - isso pode ser mostrado por um argumento de dimensão "tipo contagem", pois você precisa de n ^ 2 "locais" no circuito para colocar constantes. No entanto, dados n pares diferentes de vetores (x ^ 1, y ^ 1) ... (x ^ n, y ^ n), você pode colocar os x's nas linhas de uma matriz n * n X e, da mesma forma, os y's nas colunas de uma matriz Y e, em seguida, leia todas as respostas x ^ iAy ^ i na diagonal de XAY, onde isso é calculado em n ^ 2,3 (mais ou menos) operações usando multiplicação de matriz rápida, significativamente menor que n * n ^ 2

Noam
fonte
Obrigado, eu conheço esse exemplo. Uma similar é a existência de polinômios de grau n em uma variável que leva tempo n para avaliar em um determinado ponto (embora eu não ache que haja exemplos explícitos, estou errado?) No entanto, pode-se avaliar esse polinômio em n pontos no tempo n log ^ 2 (n).
Matt Hastings
11
Encontrei dois artigos dos anos 80 sobre o problema de soma direta algébrica: "Sobre a validade da conjectura de soma direta" de Ja'ja e Takche e "Sobre a conjectura de soma direta estendida" de Bshouty. Não consigo resumir o conteúdo deles, mas talvez eles sejam úteis.
Andy Drucker
5

Isso foi estudado e resolvido por Wolfgang Paul, que mostrou essencialmente o que é discutido.

pau lipton
fonte
2
Agradável! Existe alguma referência?
Hsien-Chih Chang # 23/04