Quão pequeno pode ser um circuito booleano em camadas para uma função com complexidade de circuito ?

Considere uma função calculada por um circuito booleano com entradas do tamanho sobre a base (com o indegree 2 para os portões ). $f$ $C$ $n$ $s(n) = \mathsf{poly}(n)$ $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ $\mathsf{XOR},\mathsf{AND}$

Um circuito booleano é colocado em camadas se puder ser disposto em camadas ( sendo a profundidade do circuito) de portas, de modo que qualquer borda entre duas portas conecte as camadas adjacentes. $d$ $d$

Dado que possui um circuito booleano de tamanho , o que podemos dizer sobre o tamanho de um circuito em camadas que computa ? Existe um limite superior trivial: adicionando nós fictícios a em cada camada atravessada por uma aresta, obtemos um circuito em camadas de tamanho no máximo . Mas podemos melhorar em geral (por exemplo, ou ) ou para uma classe interessante de circuitos? $f$ $s$ $f$ $C$ $O(s^2)$ $O(s\cdot \log s)$ $O(s)$

Fundo. Essa questão decorre de resultados recentes em criptografia que mostram como calcular com segurança circuitos booleanos em camadas de tamanho com (por exemplo, ou ; Estou tentando entender o quão restritiva essa restrição aos circuitos booleanos em camadas pode ser na prática, seja para circuitos gerais ou para circuitos "naturais". No entanto, não encontrei muito sobre circuitos em camadas na literatura; ponteiros apropriados também seriam bem-vindos. $s$ $o(s)$ $s/\log s$ $s/\log\log s)$

circuit-complexity circuits Geoffroy Couteau
fonte

Aqui está um exemplo de um circuito que parece difícil de converter em um circuito em camadas sem uma explosão significativa de tamanho. Defina como alguma função que possa ser calculada no tamanho . Definir , e deixe ser iterações de . Então tem tamanho . Parece difícil construir um circuito em camadas com tamanho menor que . Portanto, se , talvez devêssemos esperar uma lacuna entre o tamanho de um circuito e o tamanho de um circuito em camadas. Não é uma prova, apenas um exemplo sugestivo para talvez impulsionar a intuição.

f : {0, 1}^{n - 1} \to {0, 1}

$f:\{0,1\}^{n-1} \to \{0,1\}$

u

$u$

g (x_{1}, \dots, x_{n}) = (x_{2}, \dots, x_{n}, x_{1} \oplus f (x_{2}, \dots, x_{n}))

$g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$

C

$C$

t

$t$

g

$g$

C

$C$

O (t u)

$O(tu)$

Θ (n t)

$\Theta(nt)$

u = o (n)

$u=o(n)$

Tanto quanto me lembro, para circuitos em camadas, o limite inferior mais conhecido é da forma . É particularmente fácil de provar para um Para- função. Tomemos, por exemplo, um mapa linear onde possui zeros apenas na diagonal principal. Em seguida, ele deve ter pelo menos portas em todas as camadas e o número de camadas é pelo menos . Note que esta função pode ser facilmente calculada por um circuito regular do tamanho . Para funções de saída única, também é possível provar o mesmo limite inferior, mas não me lembro do argumento.

Ω (n \log n)

$\Omega(n \log n)$

n

$n$

n

$n$

A x

$Ax$

A \in {0, 1}^{n \times n}

$A \in \{0,1\}^{n \times n}$

n

$n$

\log_{2} n

$\log_2 n$

O (n)

$O(n)$

Alexander S. Kulikov

Muito obrigado pelos comentários. @ AlexanderS.Kulikov, o seu argumento é folclórico ou você tem algum indicador para trabalhar em circuitos em camadas? O faz sentido - eu ficaria muito surpreso com algo menor - mas o único limite superior conhecido?

Ω (n \log n)

$\Omega(n \log n)$

O (n^{2})

$O(n^2)$

Geoffroy Couteau

Eu acho que é um folclore, sim. Não tenho certeza se recebo a pergunta sobre limite superior. Você pode dar uma olhada no seguinte artigo: cs.utexas.edu/~panni/sizedepth.pdf

O (n^{2})

$O(n^2)$

Alexander S. Kulikov

Penso que não conhecemos uma transformação melhor que em geral. Note-se que um circuito de tamanho e profundidade pode ser transformado em um circuito de camadas de tamanho no máximo . (O que, na pior das hipóteses, nos fornece um circuito do tamanho .) Eu só queria ressaltar que se pudéssemos provar um limite inferior de no tamanho de um circuito em camadas, isso nos daria um limite inferior super-linear no tamanho dos circuitos de profundidade de log para esta função. Esta questão permanece em aberto por mais de 40 anos.

O (s^{2})

$O(s^2)$

s

$s$

d

$d$

d s

$ds$

O (s^{2})

$O(s^2)$

ω (n \log n)

$\omega(n\log{n})$

Alex Golovnev

Respostas:

Até onde eu sei, três classes de circuitos em camadas foram estudadas. Em todas essas definições, os arcos são permitidos apenas entre duas camadas adjacentes.

Um circuito é chamado síncrono ( Harper 1977 ) se todos os portões estiverem dispostos em camadas, e as entradas devem estar na camada 0. (Uma definição equivalente: para qualquer porta , todos os caminhos das entradas para têm o mesmo comprimento). $g$ $g$
Um circuito é localmente síncrono ( Belaga 1984 ) se cada entrada ocorrer exatamente uma vez, mas em uma camada arbitrária.
Um circuito é estratificado ( Gál, Jang 2010 ) se portas e entradas estiverem dispostas em camadas, as entradas podem ocorrer várias vezes em camadas diferentes. (Uma definição equivalente: para qualquer porta e porta de saída , todos os caminhos direcionados de a têm o mesmo comprimento.) $g$ $o$ $g$ $o$

É fácil ver que as três classes estão listadas da mais fraca à mais forte (e a classe de circuitos irrestritos é ainda mais forte).

Em relação ao tamanho de um circuito em camadas que computa um circuito irrestrito de tamanho , sabemos o seguinte: $s$

Qualquer circuito de tamanho pode ser calculado por um circuito síncrono / localmente síncrono / em camadas de tamanho ( Wegener 1987, Seção 12.1 ). $s$ $s^2$
Deve ser difícil encontrar uma função explícita que exija um circuito síncrono / localmente síncrono / em camadas de tamanho . Na verdade, todos os circuitos de tamanho e a profundidade pode ser calculado por um circuito síncrono de tamanho ( Wegener 1987, Secção 12.1 ). Assim, mesmo se tivermos uma função explícita que requer circuitos síncronos de tamanho (independentemente de sua complexidade na classe de circuitos irrestritos), não pode ser calculado por um circuito de profundidade e tamanho , que responde a uma pergunta aberta de longa data na complexidade do circuito ( $\omega(s\log{s})$ $s$ $d$ $O(sd)$ $f$ $\omega(n\log{n})$ $f$ $O(\log{n})$ $O(n)$ Valiant 1977 ).
Existem funções explícitas

3.1 com limite inferior para circuitos síncronos , mas limite superior para circuitos localmente síncronos ( Turán 1989 ). $\Omega(n\log{n})$ $O(n)$

3.2 com limite inferior para circuitos localmente síncronos , mas limite superior para circuitos em camadas ( Turán 1989 ). $\Omega(n\log{n})$ $O(n)$

É importante observar que esses dois resultados de separação da Turán são comprovados para funções com uma saída. Muitas vezes, é muito mais fácil encontrar uma função com saídas que separam duas dessas classes. $n$

Como um exemplo, considere a função em que o -ésimo bit de saída é um XOR de todas as entradas, excepto para o th um. Essa função pode ser facilmente calculada por um circuito em camadas do tamanho : Primeiro calcule um XOR de todas as entradas nas camadas do tamanho total , depois calcule todas as saídas em uma camada do tamanho . Por outro lado, requer circuitos síncronos de tamanho . De fato, para calcular uma paridade de comprimento , a profundidade do circuito deve ser pelo menos . Por outro lado, cada camada deve transmitir $f\colon\{0,1\}^n\to\{0,1\}^n$ $i$ $i$ $O(n)$ $\log{n}$ $n$ $n$ $f$ $\Omega(n\log{n})$ $n-1$ $\Omega(\log{n})$ $n$ bits de informação, portanto, seu tamanho deve ser pelo menos . $n$

Alex Golovnev
fonte