Circuitos aritméticos com apenas uma porta de limiar

Quando restrita a $0$ - $1$ entradas, cada $\{+,\times\}$ -circuit $F(x_1,\ldots,x_n)$ calcula uma função $F:\{0,1\}^n\to \mathbb{N}$ . Para obter uma função booleana , podemos apenas adicionar um gate limiar fanin-1 como o gate de saída. Na entrada $a\in\{0,1\}^n$ , o limite resultante $\{+,\times\}$ - ocircuitoentão gera$1$ se$F(a)\geq t$ , e gera$0$ se$F(a)\leq t-1$ ; o limite$t=t_n$ pode ser qualquer número inteiro positivo, que pode depender de$n$ mas não dos valores de entrada. O circuito resultante calcula algumafunção booleana(monótona)$F':\{0,1\}^n\to \{0,1\}$ .

Pergunta: Os limiares $\{+,\times\}$ -circuitos podem ser eficientemente simulados por $\{\lor,\land\}$ -circuitos?

Em "eficientemente", quero dizer "com no máximo um aumento polinomial de tamanho". A resposta é clara "sim" para o limiar $t=1$ : basta substituir $+$ por $\lor$ , $\times$ por $\land$ e remova a última porta do limiar. Ou seja, $\{\lor,\land\}$ -circuitos são, de fato, limiar- $1$ $\{+,\times\}$ -circuitos. Mas e quanto aos limites maiores, digamos, $t=2$ ?

Pode-se definir análogos aritméticos $\#C$ da maioria das classes de circuitos booleanos $C$ , usando $+$ vez de OR, $\times$ vez de AND e $1-x_i$ vez de $\bar{x}_i$ . Por exemplo, os circuitos $\#AC^0$ são $\{+,\times\}$ -circuitos de profundidade constante com fanin ilimitado $+$ e $\times$ portas e entradas $x_i$ e $1-x_i$ . Agrawal, Allender e Datta mostraram esse limite $\#AC^0$ = $TC^0$ . (Lembre-se de que $AC^0$ si é um subconjunto adequado de $TC^0$ ; tome, digamos, a função Maioria.) Em outras palavras, os circuitos de limiar de profundidade constante podem ser eficientemente simulados por profundidade constante $\{+,-,\times\}$ - circuitos, com apenas um portão de limiar único! Note, no entanto, que minha pergunta é sobre circuitos monótonos (sem menos " $-$ " como portões e até mesmo 1 -x i como entradas). Um (último) portão de limiar também pode ser tão poderoso? Como não conheço essas coisas, qualquer sugestão relacionada é bem-vinda. $1-x_i$

NB Há ainda outro resultado interessante devido ao Arnold Rosenbloom: { + , × } -circuitos com apenas uma função monotônica g : N 2 → { 0 , 1 }, pois o gate de saída pode calcular cada função de fatia com O ( n ) gates. Uma função de fatia é uma função booleana monótona que, para alguns k fixos , gera 0 (resp. 1 ) em todas as entradas com menos (resp., Mais) que $\{+,\times\}$$g:\mathbb{N}^2\to\{0,1\}$$O(n)$$k$$0$$1$$k$uns. Por outro lado, a contagem fácil mostra que a maioria das funções de fatia exige circuitos gerais { ∨ , ∧ , ¬ } de tamanho exponencial. Assim, uma porta de saída adicional "inocente" pode tornar onipotentes os circuitos monotônicos! Minha pergunta pergunta se isso também pode acontecer quando g : N → { 0 , 1 } é um gate limiar fanin- 1 . $\{\lor,\land,\neg\}$$g:\mathbb{N}\to\{0,1\}$$1$

Geralmente, em aplicativos, apenas limiares grandes funcionam: geralmente precisamos de limiares no formato 2 n ϵ para ϵ > 0 . Por exemplo, se F : { 0 , 1 } n → N conta o número de s - t caminhos do gráfico especificado pelo 0 - uma entrada, em seguida, para t = m m 2 com m ≈ n 1 / 3 , o threshold- t versão de F resolve$2^{n^{\epsilon}}$$\epsilon > 0$$F:\{0,1\}^n\to \mathbb{N}$ $s$$t$$0$$1$$t=m^{m^2}$$m\approx n^{1/3}$$t$$F$ a existência de um problema Hamiltoniano s - t path em gráficos m -vertex (ver, por exemplo, aqui ). $s$$t$$m$

(Adicionado em 11.11.2014): Como Emil respondeu grande parte da minha pergunta, e como o caso de limites exponenciais não está à vista, agora aceito a resposta (muito legal) de Emil.

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.

First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, and either $ab,a'b\ge t$ as well, or $ab=a'b(=0)$.

With this in mind, we can simulate the circuit with a Boolean monotone circuit by replacing each node $c$ with nodes $c_0,\dots,c_t$, where $c_i$ is intended to compute the predicate $c\ge i$. (We need $c_0$ only for notational convenience, it computes the constant $1$ function.) If $c$ is a Boolean input variable $x$, we take $c_1=x$, $c_2=\dots=c_t=0$. If $c$ is an addition gate, say $c=a+b$, we implement it via

This takes $O(t^3)$ gates per one gate of the original circuit. As a minor optimization, we can reduce it to $O(t^2)$ by putting