A complexidade do circuito é o estudo de circuitos limitados por recursos e as funções calculadas por esses circuitos.
Esta é uma pergunta sobre a complexidade do circuito. (As definições estão na parte inferior.) Yao e Beigel-Tarui mostraram que toda família de circuitos de tamanho s possui uma família de circuitos equivalente de tamanho s p o l y ( log s ) de profundidade dois , em que a porta de saída é uma...
Nos anos 80, Razborov mostrou famosa que existem funções booleanas explícitas e monótonas (como a função CLIQUE) que exigem exponencialmente muitos portões AND e OR para calcular. No entanto, a base {AND, OR} sobre o domínio booleano {0,1} é apenas um exemplo de um conjunto de portas interessante...
Ryan Williams acabou de postar seu limite inferior no ACC , a classe de problemas que têm circuitos de profundidade constantes com ventiladores e portas AND ilimitados AND, OR, NOT e MOD_m para todos os m possíveis. O que há de tão especial nos portões MOD_m? Eles permitem simular aritmética...
Seja um número inteiro positivo fixo de tamanho bits.nUMAAAnnn É permitido pré-processar esse número inteiro, conforme apropriado. Dado outro número inteiro positivo de tamanho bits, qual é a complexidade da multiplicação ?m A BBBBmmmA BABAB Observe que já temos os algoritmos . A questão aqui é...
Alguns anos atrás, Joel Friedman havia algum trabalho relacionado aos limites inferiores do circuito à cohomologia de Grothendieck (veja artigos: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ) Essa linha de pensamento trouxe novas idéias para a complexidade booleana ou continua...
Eu pensei em compartilhar esta pergunta, pois pode ser interessante para outros usuários aqui. Assume-se que uma função que é de uma classe uniforme (como ) também está em uma pequena classe não uniforme (como um C 0 / p o l y , isto é, não uniforme Um C 0 ), isso implica que a função está contido...
Seja uma função booleana e pensemos em f como uma função de a . Nesta linguagem, a expansão de Fourier de f é simplesmente a expansão de f em termos de monômios quadrados livres. (Esses monômios formam uma base para o espaço de funções reais em . A soma dos quadrados dos coeficientes é simplesmente...
Em seu livro Boolean Function Complexity, Stasys Jukna menciona (página 564) que Kolmogorov acreditava que toda linguagem em P possui circuitos de tamanho linear. Nenhuma referência é mencionada e não consegui encontrar nada online. Alguém sabe mais sobre
Na complexidade computacional, existe uma distinção importante entre cálculos monótonos e gerais e um famoso teorema de Razborov afirma que 3-SAT e até MATCHING não são polinomiais no modelo monótono de circuitos booleanos. Minha pergunta é simples: existe um análogo quântico para circuitos...
Qual é a complexidade de decidir se um circuito com bits de entrada e bits de saída calcula uma permutação de ? em outras palavras, se cada bit em é uma saída do circuito para alguma entrada? Parece um problema que foi estudado, mas não consigo encontrar nenhuma referência.N C0 0NC0...
Recentemente, Ryan Willams provou que a Construtividade na Prova Natural é inevitável para derivar uma separação de classes de complexidade: N E X PNEXP\mathsf{NEXP} e . T C0 0TC0 0\mathsf{TC}^{0} A construtividade na prova natural é uma condição que todas as provas combinatórias na complexidade...
Questão: Qual é o limite inferior do tamanho da fórmula mais conhecido para uma função explícita no AC 0 ? Existe uma função explícita com um limite inferior Ω(n2)Ω(n2)\Omega(n^2) ? Fundo: Como a maioria dos limites inferiores, os limites inferiores do tamanho da fórmula são difíceis de...
Desculpas por fazer uma pergunta que certamente deve estar em muitas referências padrão. Estou curioso sobre exatamente a pergunta no título, em particular estou pensando em circuitos booleanos, sem limite de profundidade. Coloquei "menor" entre aspas para permitir a possibilidade de haver várias...
EDIT (v2): Adicionada uma seção no final sobre o que eu sei sobre o problema. EDIT (v3): adicionada discussão sobre o grau do limiar no final. Questão Esta pergunta é principalmente uma solicitação de referência. Eu não sei muito sobre o problema. Quero saber se já houve trabalho anterior sobre...
Na pesquisa "Circuitos Quânticos de Profundidade Pequena" de D. Bera, F. Green e S. Homer (p. 36 da ACM SIGACT News, junho de 2007 vol. 38, n. 2) , li a seguinte frase: A versão clássica de (na qual as portas e têm fanout no máximo constante) é comprovadamente mais fraca que...
Um polinômio é uma projeção monótona de um polinômio g ( y 1 , … , y m ) se m = poli ( n ) , e existe uma atribuição π : { y 1 , … , y m } → { x 1 , … , x n , 0 , 1f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)g(y1,…,ym)g(y1,…,ym)g(y_1,\ldots,y_m)mmm(n)(n)(n) tal que f ( x 1 , … , x n ) = g ( π ( y 1 ) , …...
O estado de nosso conhecimento sobre circuitos aritméticos gerais parece ser semelhante ao estado de nosso conhecimento sobre circuitos booleanos, ou seja, não temos bons limites inferiores. Por outro lado, temos limites inferiores de tamanho exponencial para circuitos booleanos monótonos . O...
À luz do resultado recente do abismo na profundidade 3 (que, entre outras coisas, produz profundidade-3 circuito aritmético para onxndeterminante sobreC), que têm as seguintes questões: Grigoriev e Karpinskirevelouum2Ω(n)um limite inferior para qualquer profundidade-3 circuito aritmético de...
Existe alguma hipótese plausível de complexidade / criptografia que exclua a possibilidade de que os circuitos de tamanho polinomial tenham tamanho subexponencial (isto é, com ϵ < 1 ) de profundidade limitada
captura a idéia de eficientemente paralelizável, e uma interpretação disso são problemas que são solucionáveis no tempo O ( log c n ) usandoprocessadores paralelos O ( n k ) para algumas constantes c , k . Minha pergunta é se existe uma classe de complexidade análoga em que o tempo é n c e o...