<p>I was curious if something like that is known or was studied.</p>

<p>Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.</p>

<p>Now let's consider general circuits: gates are $\{\vee,\wedge,\neg\}$ of fun-in at most $2$, no depth restrictions. </p>

<p>Let's call a circuit nice if in all gates it computes only simple functions. That immediately implies that if a function is not simple it can not be computed by a nice circuit.</p>

<p>My question is: do we know some simple function that is not computable by linear-size nice circuit? How about other definitions of simple or different models, like arithmetic circuits?</p>

CC BY-SA 3.0
2017-09-01T12:12:42.037Z
What does "in all gates it computes only simple functions" mean? If "the functions computed at all gates are simple", then nice circuits = $AC^0$ circuits. If this means "each gate must be simple", then nice circucits include general $\{\lor,\land,\neg\}$ circuits.
Stasys
CC BY-SA 3.0
2017-09-01T12:28:12.507Z
Yes, I've meant that functions at all gates are simple. However, the circuit has no bounds depth. I don't see immediately why this is the same as $AC_0$.
ivmihajlin
CC BY-SA 3.0
2017-09-01T13:00:01.003Z
The output gate is also a gate.
Stasys
CC BY-SA 3.0
2017-09-01T13:04:50.243Z
Yes. I agree, that we can only compute simple functions with nice circuits. But I want a lower bound (even a very weak one) for a concrete simple function, rather than a function not computable by such circuits. Maybe I'm missing something very simple...
ivmihajlin
CC BY-SA 3.0
2017-09-01T15:40:18.637Z
"Yes, I've meant that functions at all gates are simple". So, if $f$ is a simple function, why it cannot be computed by a nice circuit with just 1 gate $f$? If only gates (not the functions *computed* at these gates, as you require) must be simple, then you are actually asking *much* more than for a nonlinear lower bound on the size of $\{\lor,\land,\neg\}$ circuits for an $AC^0$ function. But we do not know such a bound even for functions in NP.
Stasys
CC BY-SA 3.0
2017-09-01T16:17:55.547Z
Oh no, the functions are in the gates are simple, but the circuit is still over $\{\vee,\wedge,\neg\}$. This model, at least that's what I expect, should be a lot less powerful than the general circuits.
 I'll rewrite the question to make it less confusing.
ivmihajlin
CC BY-SA 3.0
2017-09-01T22:50:01.240Z
It seems that the op is asking whether there is a function in AC_0 that is know not to be computable by a fan-in 2 circuit of linear size with the restriction that each gate computes  an AC_0 function. Without this restriction the answer seems to be unknown even for functions in NP.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-09-02T01:27:55.613Z
I think it would be good if you distinguish between syntactic structure of the circuit and Bikram functions computer by each gate. What are the gates in the circuit? Is your restriction on complexity of gate themselves or complexity of Boolean functions computer by them? In either case I think Stasys's comment contains the answer: either you have general enough gates that make the class not really restricted or you have restricted the Boolean functions computed at each gate which implies that the output of whole circuit belongs to that restriction.
Kaveh
CC BY-SA 3.0
2017-09-02T08:17:33.730Z
@Kaveh The op already clarified that the gate set is fan-in 2 OR,AND and NOT. It is the function computed at each gate that is simple. Why does Stasys' comment answers the question?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-09-02T09:08:53.593Z
@Mateus: so, we have standard fanin-in 2 circuits with a *semantic* restriction that at no gate a function outside $AC^0$ (like parity) can be computed. This already makes sense. To understand the model, one needs to understand "fanin vs. depth" tradeoff: examples of $AC^0$ functions $f$ requiring many gates in $AC^0$ (constant depth) circuits but having small nice circuits of quickly growing depth. Without the restriction "nice", already parity function shows the gap.
Stasys
<circuit-complexity><lower-bounds><arithmetic-circuits>
Circuit's with gate computing only "simple" functions
ivmihajlin
# Circuit's with gate computing only "simple" functions

(Asked by: username_0 on 2017-09-01)

I was curious if something like that is known or was studied.

Let's call a function simple if it is computable by $AC\_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.

Now let's consider general circuits: gates are $\{\vee,\wedge,\neg\}$ of fun-in at most $2$, no depth restrictions.

Let's call a circuit nice if in all gates it computes only simple functions. That immediately implies that if a function is not simple it can not be computed by a nice circuit.

My question is: do we know some simple function that is not computable by linear-size nice circuit? How about other definitions of simple or different models, like arithmetic circuits?

**Tags:** circuit-complexity, lower-bounds, arithmetic-circuits
> **Comments:**
> **username_1**: What does "in all gates it computes only simple functions" mean? If "the functions computed at all gates are simple", then nice circuits = $AC^0$ circuits. If this means "each gate must be simple", then nice circucits include general $\{\lor,\land,\neg\}$ circuits.  
> **username_0**: Yes, I've meant that functions at all gates are simple. However, the circuit has no bounds depth. I don't see immediately why this is the same as $AC_0$.  
> **username_1**: The output gate is also a gate.  
> **username_0**: Yes. I agree, that we can only compute simple functions with nice circuits. But I want a lower bound (even a very weak one) for a concrete simple function, rather than a function not computable by such circuits. Maybe I'm missing something very simple...  
> **username_1**: "Yes, I've meant that functions at all gates are simple". So, if $f$ is a simple function, why it cannot be computed by a nice circuit with just 1 gate $f$? If only gates (not the functions *computed* at these gates, as you require) must be simple, then you are actually asking *much* more than for a nonlinear lower bound on the size of $\{\lor,\land,\neg\}$ circuits for an $AC^0$ function. But we do not know such a bound even for functions in NP.  
> **username_0**: Oh no, the functions are in the gates are simple, but the circuit is still over $\{\vee,\wedge,\neg\}$. This model, at least that's what I expect, should be a lot less powerful than the general circuits.  I'll rewrite the question to make it less confusing.  
> **username_2**: It seems that the op is asking whether there is a function in AC_0 that is know not to be computable by a fan-in 2 circuit of linear size with the restriction that each gate computes  an AC_0 function. Without this restriction the answer seems to be unknown even for functions in NP.  
> **username_3**: I think it would be good if you distinguish between syntactic structure of the circuit and Bikram functions computer by each gate. What are the gates in the circuit? Is your restriction on complexity of gate themselves or complexity of Boolean functions computer by them? In either case I think Stasys's comment contains the answer: either you have general enough gates that make the class not really restricted or you have restricted the Boolean functions computed at each gate which implies that the output of whole circuit belongs to that restriction.  
> **username_2**: @Kaveh The op already clarified that the gate set is fan-in 2 OR,AND and NOT. It is the function computed at each gate that is simple. Why does Stasys' comment answers the question?  
> **username_1**: @Mateus: so, we have standard fanin-in 2 circuits with a *semantic* restriction that at no gate a function outside $AC^0$ (like parity) can be computed. This already makes sense. To understand the model, one needs to understand "fanin vs. depth" tradeoff: examples of $AC^0$ functions $f$ requiring many gates in $AC^0$ (constant depth) circuits but having small nice circuits of quickly growing depth. Without the restriction "nice", already parity function shows the gap.  

---

## 0 answers

