Circuito de limites mais baixos sobre conjuntos arbitrários de portas

40

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 que deixa de ser universal. Isso leva à minha pergunta:

Existe algum outro conjunto de portas, curiosamente diferente das portas monótonas, para as quais são conhecidos limites inferiores exponenciais no tamanho do circuito (sem profundidade ou outras restrições no circuito)? Caso contrário, existe algum outro conjunto de portas que seja um candidato plausível para limites inferiores - limites que não exigiriam necessariamente romper a barreira das Provas Naturais, como o resultado dos circuitos monótonos de Razborov não?

Se esse conjunto de portas existir, certamente será sobre um alfabeto k-ário para k≥3. A razão é que, sobre um alfabeto binário, o

(1) portões monótonos ({AND, OR}),

(2) portões lineares ({NOT, XOR}) e

(3) portões universais ({AND, OR, NOT})

esgotam basicamente as possibilidades interessantes, como se segue no teorema da classificação de Post. (Observe que eu assumo que as constantes --- 0 e 1 no caso binário --- estejam sempre disponíveis gratuitamente.) Com as portas lineares, todas as funções booleanas f: {0,1} n → {0,1} são computável é computável por um circuito de tamanho linear; com um conjunto universal, é claro que estamos enfrentando provas naturais e outras barreiras aterrorizantes.

Por outro lado, se considerarmos conjuntos de portas ao longo de um alfabeto de 3 ou 4 símbolos (por exemplo), um conjunto mais amplo de possibilidades se abre --- e pelo menos que eu saiba, essas possibilidades nunca foram totalmente mapeadas do ponto de vista da teoria da complexidade (corrija-me se estiver errado). Eu sei que os possíveis conjuntos de portas são estudados extensivamente sob o nome de "clones" na álgebra universal; Eu gostaria de estar mais familiarizado com essa literatura para saber o que significaria os resultados dessa área para a complexidade do circuito.

De qualquer forma, não parece fora de questão que existem outros limites dramáticos mais baixos para a prova, se simplesmente expandirmos a classe de conjuntos de portas sobre alfabetos finitos que estamos dispostos a considerar. Se eu estiver errado, por favor me diga o porquê!

Scott Aaronson
fonte
3
Se você considerar as funções , a situação estará mais envolvida para portas lineares, porque o argumento de contagem mostra que existem funções que requerem Ω ( n 2f:{0,1}n{0,1}nportas a serem computadas, embora, tanto quanto eu saiba, não haja exemplos explícitos de funções que exijam circuitos de tamanho superlinear. Ω(n2log(n))
Grigory Yaroslavtsev
2
Apenas uma observação: se você substituir portas booleanas monótonas por portas que calculam quaisquer funções reais não decrescentes , também obtém limites inferiores exponenciais no tamanho dos circuitos. Isso foi provado por Pudlak: limites mais baixos para resolução e provas de planos de corte e cálculos monótonos , J. of Symb. Logic 62 (3), 1997, pp.981-998.
Iddo Tzameret 30/09/10
2
Grigory: Obrigado; Eu debati se deveria mencionar isso no OP! Você está certo que não temos nenhum limite inferior superlinear explícito no número de portas XOR necessárias para calcular uma função linear f: {0,1} <sup> n </sup> & rarr; {0,1} < sup> n </sup>. Por outro lado, não é difícil encontrar candidatos para transformações lineares que <i> deveriam </i> exigir & Omega; (n log n) portões XOR (a transformada de Fourier, a matriz "Sierpinski Gasket" ...) e Bram Cohen propuseram uma função de exemplo que deveria exigir portas XOR do Omega (n <sup> 3/2 </sup>) (não me lembro, mas poderia perguntar a ele).
Scott Aaronson
Mesmo para o tamanho do alfabeto 3, a rede de clones é incontável e contém todas as redes finitas como sub-rede. Portanto, existem infinitas bases de operações possivelmente interessantes a serem consideradas. Não conheço nenhum trabalho sobre o uso de clones não-booleanos para limites mais baixos do circuito, mas isso parece valer a pena investigar com mais profundidade.
András Salamon
3
Scott, você conhece um analógico apropriado para a classe AC ^ 0 em aphabets maiores? Permitam-me também observar que se pode considerar noções de monotonicidade para alfabetos maiores (Elchanan Mossel e eu escrevemos sobre limiares acentuados para aqueles que estão na frente . monotonicidade.
Gil Kalai

Respostas:

25

(Removido dos comentários, conforme sugerido por Suresh. Observe que alguns erros no comentário foram corrigidos aqui.)

Obrigado a Scott por uma ótima pergunta.

Scott parece sugerir que o motivo da dificuldade dos limites inferiores pode ser o idioma restrito das operações no caso booleano. O argumento de contagem de Shannon, que mostra a maioria dos circuitos, deve ser grande, depende da diferença entre a potência expressiva contável e incontáveis ​​muitos circuitos. Essa lacuna parece desaparecer quando o alfabeto possui pelo menos três símbolos.

Para o tamanho do alfabeto 2 (o caso booleano), a rede de clones é contada infinitamente e é chamada de rede de Post .

Imagem de treliça do Post da Wikipedia

A estrutura de Post também esclarece por que existem apenas algumas bases de operações interessantes para o caso booleano.

Para o tamanho do alfabeto 3 ou superior, a treliça dos clones é incontável. Além disso, a rede não satisfaz qualquer identidade não trivial da rede, portanto, parece impossível fornecer uma descrição completa da rede. Para o tamanho do alfabeto 4 ou superior, a rede de clones na verdade contém todas as redes finitas como um sub-rede. Portanto, existem infinitas bases de operações possivelmente interessantes a serem consideradas quando o alfabeto possui 3 ou mais símbolos.

  • Bulatov, Andrei A., Condições satisfeitas por redes de clones , Algebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Scott perguntou ainda: a estrutura de clones permanece incontável se assumirmos que as constantes estão disponíveis gratuitamente?

A resposta é que sim, veja, por exemplo

  • Gradimir Vojvodić, Jovanka Pantović e Ratko Tošić, O número de clones que contêm uma função unária , NSJOM 27 83-87, 1997. ( PDF )
  • J. Pantović, R. Tošić e G. Vojvodić, A cardinalidade de álgebras funcionalmente completas em um conjunto de três elementos , Algebra Universalis 38 136–140, 1997. doi: 10.1007 / s000120050042

embora aparentemente isso tenha sido publicado anteriormente:

  • Ágoston, I., Demetrovics, J. e Hannák, L. Sobre o número de clones contendo todas as constantes , Coll. Matemática. Soc. János Bolyai 43 21–25, 1983.

Uma boa declaração específica é de:

  • A. Bulatov, A. Krokhin, K. Safin e E. Sukhanov, Sobre a estrutura das redes de clones , In: "Álgebra Geral e Matemática Discreta", editores: K. Denecke e O. Lueders, 27-34. Heldermann Verlag, Berlim, 1995. ( PS )

k3Lk20

Para finalizar, não conheço nenhum trabalho sobre o uso de clones não booleanos para os limites inferiores do circuito. Parece valer a pena investigar com mais profundidade. Dado o relativamente pouco que se sabe sobre a rede de clones, pode haver bases interessantes de operações esperando para serem descobertas.

Mais ligações entre a teoria dos clones e a ciência da computação provavelmente também seriam de grande interesse para os matemáticos que trabalham com álgebra universal. Um exemplo anterior desse tipo de interação surgiu quando Peter Jeavons mostrou que álgebras podiam ser associadas a linguagens de restrição, de uma maneira que permite que os resultados de rastreabilidade sejam traduzidos em propriedades da álgebra. Andrei Bulatov usou isso para provar a dicotomia para CSPs com tamanho de domínio 3. No outro sentido, houve um reavivamento do interesse na teoria da congruência mansa como resultado da aplicação da ciência da computação. Eu me pergunto o que seguiria de um link entre a teoria dos clones e a complexidade do circuito não-booleano.

András Salamon
fonte
Muito obrigado, András! Vou verificar o artigo de Ágoston et al. quando eu tiver uma chance. Enquanto isso, examinei a lista de clones pré-completos máximos em um conjunto de 3 elementos de Pantović et al. artigo ao qual você vinculou, e não acho que nenhum deles seja candidato a "novos" limites inferiores do circuito. (Para alguns deles, os limites inferiores exponenciais seguem imediatamente do limite inferior monótono de Razborov; para outros, precisaríamos de limites inferiores para circuitos gerais ou circuitos lineares.) Mas mesmo no caso k = 3, clones menores que os pré-completos ainda parece valer a pena olhar.
11138 Scott Aaronson
15

Isso é movido dos comentários, como sugeriu Suresh.

f:0,1n0,1nΩ(n2log(n))

n2log(n)cc

Ω(nlogn)Ω(n3/2)

Edit 2. O principal obstáculo é que não temos métodos para provar limites inferiores não lineares, mesmo para portões lineares, tanto quanto eu sei (para limites inferiores lineares, pode-se usar a eliminação de gate, que é muito improvável que limites lineares). Embora pareça que alguns métodos da álgebra linear sejam realmente úteis. Portanto, apresentar candidatos é bom, mas de qualquer maneira são necessários alguns novos métodos.

Grigory Yaroslavtsev
fonte
11
  1. {0,1}aZ3n={0,1,2}nmin(x,y)xymod2a 0 2 a 1 2 n / f(a)=0a02's em é pelo menos o número de ' s. Ele mostra que qualquer base de circuito (acima do MIN / XOR) requer cerca de portas para calcular . Mas foi isso! Não tenho conhecimento de nenhum resultado adicional em um favor semelhante (indo para domínios maiores, mas ainda finitos), exceto, é claro, o material dos circuitos aritméticos. Mas apenas para circuitos - para programas de ramificação que vão para domínios maiores, torna mais fácil a tarefa de limites mais baixos. a1 f2n/nf

  2. Em circuitos com portas XOR. Aqui, mesmo o caso da profundidade é amplamente aberto. Os limites inferiores mais altos para transformações lineares explícitas sobre têm a forma . Provar um limite como para uma constante , mesmo na profundidade e mesmo que apenas portas XOR sejam permitidas, é um desafio.y = A x G F ( 2 )2y=AxGF(2)n 1 + c c > 0 2nlog3/2nn1+cc>02

Stasys
fonte
2
Caro Stasys, posso sugerir que você registre sua conta? Isso permitirá que você use a mesma conta de usuário para postar respostas e editá-las posteriormente, entre outras coisas. (Deixe-me saber se você decidir se registrar e eu vou mesclar suas contas anteriores com ele assim que você também pode editar suas mensagens anteriores.)
Kaveh
11
Obrigado, Kaveh, eu me registrei agora. A sugestão de Scott (vá para domínios maiores) também pode ser interessante do ponto de vista "pragmático". Digamos, qual é o menor número de portas max / plus em um circuito para o problema de Subconjunto-Soma com a capacidade da mochila ? Para simular o algoritmo de programação dinâmica padrão, é suficiente permitir adicionalmente que os fios façam testes para números inteiros em nosso domínio. Este algoritmo também fornece um limite superior no número de portas. Problema: prove que os portões são necessários. Isso significa que o DP não pode fazer melhor com a mochila. x i = a a n K Ω ( n K )Kxi=aanKΩ(nK)
Stasys