Existe um limite inferior melhor que o linear para fatoração e log discreto?

Existem referências que fornecem detalhes sobre os limites inferiores do circuito para problemas difíceis específicos que surgem na criptografia, como fatoração inteira, problema de logaritmo discreto prime / composto e sua variante sobre o grupo de pontos de curvas elípticas (e suas variedades abelianas de maior dimensão) e os aspectos gerais problema de subgrupo oculto?

Especificamente, algum desses problemas tem mais do que um limite inferior de complexidade linear?

@ Suresh: seguindo o seu conselho, aqui está a minha "resposta". O status dos limites inferiores do circuito é bastante deprimente. Aqui estão os "registros atuais":

• para circuitos acima de { ∧ , ∨ , ¬ } e 7 n - 7 para circuitos acima de$4n-4$$\{\land,\lor,\neg\}$$7n-7$ e { ∨ , ¬ } computação ⊕ n ( x ) = x 1 ⊕ x 2 ⊕ ⋯ ⊕ x n ; Redkin (1973). Esses limites são apertados. $\{\land,\neg\}$$\{\lor,\neg\}$$\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$
• para circuitos sobre a base com todas as portas fanin-2, exceto a paridade e sua negação; Iwama e Morizumi (2002). $5n-o(n)$
• para circuitos gerais sobre a base com todos os portões fanin-2; Blum (1984). Arist Kojevnikov e Sasha Kulikov de Petersburg ter encontrado uma prova simples de um ( 7 / 3 ) n - S ( 1 ) um limite inferior. A vantagem de sua prova é sua simplicidade, não numérica. Mais tarde, eles deram uma prova simples de 3 n - o ( 1 ) de limite inferior para circuitos gerais (todos os portões fanin-2 são permitidos). Embora para funções muito complicadas - dispersores afins. Os artigos estão onlineaqui. $3n-o(n)$$(7/3)n-o(1)$$3n-o(1)$
• para fórmulas acima de { ∧ , ∨ , ¬ } ; Hastad (1998). $n^{3-o(1)}$$\{\land,\lor,\neg\}$
• para geral fanin-$\Omega(n^2/\log n)$$2$ fórmulas, para programas de ramificação deterministas, e Ω ( n 3 / 2 / log n ) para programas de ramificação nondeterministic; Nechiporuk ~ (1966). $\Omega(n^2/\log^2 n)$$\Omega(n^{3/2}/\log n)$

Portanto, sua pergunta "Especificamente algum desses problemas tem mais do que um limite inferior de complexidade linear?" permanece amplamente aberto (no caso de circuitos). Meu apelo a todos os jovens pesquisadores: vá em frente, essas "barreiras" não são inquebráveis! Mas tente pensar de uma "maneira não natural", no sentido de Razborov e Rudich.