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.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.
fonte
"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 / logn ) m f O ( 2n/ n) m = 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)
fonte
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
fonte
Isso foi estudado e resolvido por Wolfgang Paul, que mostrou essencialmente o que é discutido.
fonte