# Class of languages recognizable by n-bit formulas of size at most $T(n)$

A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

1. fan-in=2 for the AND and OR nodes
2. fan-n=1 for the NOT nodes
3. fan-in=0 for the IN nodes
4. fan-out=0 to exactly one node (the OUT node)
5. Unbounded fan-out to the rest of the nodes (but the OUT node)

A Boolean formula is a Boolean circuits with fan-out $$\leq$$ 1 to all of the nodes.

Let us denote by $$C(T(n))$$ the class of all languages recognizable by n-bit formulas of size (in the meaning of Boolean circutit size) at most T(n).

Let us denote by $$\text{Size}(T(n))$$ the class of all languages recognizable by n-bit Boolean circuits of size at most $$T(n)$$.

1. What is the relationship between $$C(T(n))$$ and $$\text{Size}(T(n))$$?
2. Is $$C(T(n))$$ a well-known class? What is its name in the literature?
• Functions computed by polysize formulas constitute the well-known class NC$^1$. – Yuval Filmus Jan 26 at 3:36