2
$\begingroup$

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?
Improve this question
$\endgroup$
1
  • $\begingroup$ Functions computed by polysize formulas constitute the well-known class NC$^1$. $\endgroup$
    – Yuval Filmus
    Commented Jan 26, 2020 at 3:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.