Creio que as respostas a essa pergunta dão classes de tal forma que, para todos os polinômios ,
existe um problema na classe que não possui circuitos de tamanho p ( n ) .
No entanto, estou perguntando sobre o tamanho do circuito ω
.
é super-linear, mas não .
Embora esse comportamento par-ímpar possa ser tratado com preenchimento, pode-se
ter faixas extremamente longas de valores super-polinomiais entre valores baixos.)
circuit-complexity
lower-bounds
Comunidade
fonte
fonte
Respostas:
e P P são ambos conhecidos por não ter n k -circuitos para qualquer k fixa e não existe contenção conhecido entre eles. Detalhes no meupost.Sp2 PP nk
Atualização: Como aponta Rickey Demer, esses resultados não fornecem necessariamente um idioma com um limite inferior para todos os em S p 2 . Eu acho que o Δ p 3 é provavelmente o mais conhecido. Como o P P possui conjuntos completos, você pode obter um limite para n , mas eu não tenho uma prova completa.n Sp2 Δp3 PP n
fonte
Seja dMCSP a versão decisória do problema de tamanho mínimo de circuitoP(NPdMCSP[1])
ω(nk)
e deixe "[1]" indicar " apenas 1 consulta ".
A resposta à questão parece ser , Que na verdade é tal que, para cada número inteiro k positivo, que tem umω
fonte