Os circuitos de profundidade 2 com portas OR e MOD não são universais?

É sabido que toda função booleana pode ser realizada usando um circuito booleano de profundidade 2 (sobre as variáveis, negação e valores constantes) contendo portas AND na primeira nível e um único portão OR no nível superior; isso é simplesmente a representação DNF de . $f:\{0,1\}^n\to \{0,1\}$ $f$

Outro tipo de porta que é de grande interesse na complexidade do circuito é a porta . A definição usual é a seguinte: $MOD_m$

{M O D}_{m} (x_{1}, \dots, x_{k}) = {\begin{cases} 1 & if \sum x_{i} \equiv 0 \mod m \\ 0 & if \sum x_{i} ≢ 0 \mod m \end{cases}

$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if $\sum x_i \equiv 0 \mod m$ \\ 0 & if $\sum x_i \not\equiv 0 \mod m$ \\ }$

Esses portões às vezes têm um poder surpreendente; por exemplo, qualquer função booleana pode ser representada por um circuito de profundidade 2 com apenas portas (isso é folclore, mas eu posso elaborar se alguém estiver interessado). $\mathrm{MOD}_6$

$\mathrm{MOD}_m$ $m$ $m$ $\mathrm{OR} \circ \mathrm{MOD}_m$

Estou procurando uma prova para esta reivindicação, ou pelo menos alguma direção.

complexity-theory logic circuits Gadi A
fonte

No primeiro parágrafo, você NÃO precisa de portas ou precisa dizer "todas as funções booleanas monótonas ".

Tsuyoshi Ito

Você está certo; a suposição usual é que você tenha como entradas as variáveis, sua negação e também valores arbitrários (importantes para modgates). Vou escrever isso explicitamente.

Gadi A

n

$n$

n

$n$

Sim, desculpe por isso.

Gadi A

Estou interessado nisso. Você conhece alguma referência para o primeiro fato folclórico? Eu me pergunto, se na última classe de circuitos você permite apenas uma OU, quantos você permite na primeira?

Juan Bermejo Vega

$\text{OR} \circ \text{MOD}$

Kristoffer Arnsfelt Hansen
fonte

Não, ele está correto. A suposição implícita aqui é que n é constante e devemos ser capazes de lidar com um número arbitrariamente grande de entradas com mod_n gates.

Gadi A

@GadiA Ah, ok. Isso não ficou claro na sua pergunta, pelo menos para pessoas que não estão familiarizadas com o campo. Fiz uma edição menor que deve esclarecer isso.

Gilles 'SO- stop be evil'

Sim, minha pergunta foi muito mal formulada, desculpe.

Gadi A

@Gilles Você pode me explicar que fan-in aqui consideramos? O problema para mim é que não consigo entender por que o subcircuito do MOD não pode computar AND? Quantas entradas tem esse MOD e esse AND?

Os circuitos de profundidade 2 com portas OR e MOD não são universais?

Respostas: