É

23

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 .QAC0ANDORAC0

Uma referência para esta reivindicação está ausente. Vou chamar essa classe de , em que significa "fanout limitado". (O Zoológico da Complexidade está desativado e não posso verificar se essa classe já tem um nome na literatura). Se assumirmos fanout ilimitado para os bits de entrada, esses circuitos parecerão equivalentes a fórmulas de profundidade constante até um aumento polinomial no tamanho, de modo que a reivindicação acima não faz sentido. Em vez disso, se assumirmos fanout limitado também para os bits de entrada, não consigo pensar em nenhum idioma que separa essa classe de . Um possível candidato pode ser o idioma , ou seja , o idioma das strings com apenas um 1. É fácil mostrarACbf0bfAC0X:={x|weight(x)=1}XAC0 , mas não consegui provar que .XACbf0

As perguntas são:

É realmente mais fraca do que ? Se for, alguma ideia ou referência sobre como provar isso? E qual é a linguagem que separa essas duas classes? E o ?ACbf0AC0X

Alessandro Cosentino
fonte
6
A saída do ventilador dos bits de entrada tornará o circuito de tamanho linear. Qualquer função AC0 que exija tamanho super-linear os separará.
Kaveh
2
@ Kaveh: Talvez você possa repassar isso como resposta, talvez com um exemplo de função explícita que exija circuitos de tamanho super-linear AC0 e talvez uma referência que mostre o limite inferior do tamanho? (Ou incluir o argumento na sua resposta, se é muito simples?)
Robin Kothari
2
@Kaveh Obrigado. Eu não sabia que a separação entre e circuitos de profundidade constante de tamanho linear (aparentemente chamados ) era conhecida. A referência é "Restrições determinísticas na complexidade do circuito", de S. Chaudhuri e J. Radhakrishnan. @Kaveh Você pode responder ao seu comentário? AC0LC0
Alessandro Cosentino
2
Conforme discutido na pergunta subsequente cstheory.stackexchange.com/questions/7447/… , é igual à fórmula de tamanho linear. ACbf0
domotorp

Respostas:

23

Um limite na saída dos bits e portas de entrada tornará o tamanho do circuito linear. Seja um limite na abertura dos portões e entradas. É um DAG com grau máximo de saída limitado por ke caminho máximo de comprimento d . O número de fios disponíveis em cada nível pode aumentar k vezes, e o número de fios disponíveis no topo é k n ; portanto, o número total de fios no circuito é no máximo k n d i = 0 k ik d + 1 n que é O ( n ) .kkdkknkni=0dkikd+1nO(n)

Qualquer função que exija tamanho super-linear separará a classe de funções com uma saída limitada (aplicada também aos bits de entrada) de A C 0 . aqui estão alguns exemplos:AC0AC0

  1. [CR96]: Uma função que precisa de tamanho super-linear é a 1AC0 - seletor aproximado14. A - seletor aproximado é qualquer função cujo valor seja:14

    • sempre que o número de 1 s for no máximo n01 ,n4
    • sempre que o número de 0 s for no máximo n10 ,n4
    • pode ser ou 1 caso contrário.01
  2. [Ros08] mostra que a classe tem complexidade de funções A C 0 n Θ ( k ) ( n 2 bits de entrada são possíveis arestas de um gráfico com n vértices). Isso fornece um tamanho de linha super inferior para k > 2 .kAC0nΘ(k)n2nk>2

  3. Provavelmente é possível generalizar o exemplo em 2 can para a existência de qualquer subestrutura induzida fixa não trivial (exigindo mais de um bit) em uma dada estrutura não ordenada, por exemplo:

    • existência de um caminho de comprimento 2 em um dado gráfico,
    • ,#1(x)=2

    uma vez que requerem um número super constante de portas, dependendo de um bit que não é possível em .ACbf0

  4. O exemplo mais fácil é um portão duplicador, ou seja, um portão que cria cópias do seu bit de entrada. Isso não é possível em A C 0 b f, pois apenas O ( 1 ) de portas pode depender de cada bit de entrada.ω(1)ACbf0O(1)

Além disso, qualquer circuito de tamanho S pode ser transformado em uma fórmula de tamanho no máximo k d S e, portanto, possui uma fórmula A C 0 b f de tamanho k 2 d + 1 n, de modo que qualquer função de A C 0 superlinear a complexidade da fórmula não estará em A C 0 b f .ACbf0SkdSACbf0k2d+1nAC0ACbf0


Referências:

[CR96] S. Chaudhuri e J. Radhakrishnan, " Restrições determinísticas na complexidade do circuito ", 1996

[Ros08] Benjamin Rossman, " Sobre a complexidade em profundidade constante do k-Clique ", 2008

[Juk] Stasys Jukna, " Complexidade da função booleana: avanços e fronteiras ", rascunho

Kaveh
fonte
12
Uma separação mais recente entre e A C 0 segue deste resultado devido a Benjamin Rossman. Ele mostra que, para toda constante k (também alguma k crescente ) e constante d , qualquer circuito de profundidade d para a classe k em um gráfico de n vértices deve ter tamanho Ω ( n k / 4 ) . Isso implica que a hierarquia de idiomas aceita pelos circuitos A C 0 de tamanho n k (para diferentes kLC0AC0kkddknΩ(nk/4)AC0nkk) é realmente infinito.
Srikanth
1
Atualizei a resposta, graças a Alessandro, domotorp, Robin, Srikanth e Stasys.
Kaveh
1
@ Kaveh: Tudo bem, obrigado. Se você encontrar uma maneira de ajustar o resultado de Rossman, ficarei interessado em ouvi-lo. Quanto à função de limite-2, eu acho que nós podemos mostrar que não é nesta classe, observando que todas as funções desta classe têm fórmulas lineares de tamanho, e limite-2 tem um tamanho de fórmula limite inferior de . Ω(nlogn)
Robin Kothari
1
@ Kaveh: Se por , você quer dizer o caminho do comprimento k , lembre-se de que existem circuitos A C 0 de tamanho 2 k n O ( 1 ) para essas funções (isso segue essencialmente a técnica de código de cores de Alon, Yuster e Zwick). Não tenho certeza de que a técnica de Rossman dê esse tipo de limite (embora eu não saiba de nenhuma razão para isso não acontecer). PkkAC02knO(1)
Srikanth
1
@ Kaveh: me desculpe, eu deveria ter fornecido uma referência. O documento que você indicou iniciou o método de codificação por cores para encontrar caminhos e outros subgráficos rapidamente. Amano, neste artigo, foi o primeiro a apontar que os algoritmos poderiam ser implementados em . AC0
Srikanth