Given a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ and a Boolean basis for circuit gates $B$ (for instance $B = \{AND, OR\}$), we can construct the set of size optimal synchronous (Harper 1977) circuits for computing $f$, what I'll call $\mathcal{C}(f)$, on that basis. Given some circuit $C \in \mathcal{C}(f)$, we can slice it at each layer and, where the width of layer $i$ is $w_i$ and the depth of the circuit is $d$, we induce functions $g_0, g_1, \cdots, g_i, \cdots, g_d$ where $g_i : \{0, 1\}^n \rightarrow \{0, 1\}^{w_i}$. These functions can each be seen as inducing a new partition, or equivalence relation, of $\{0, 1\}^n$, which I'll define

$ P_i = \{\{ x \mid x \in \{0, 1\}^n, f(x) = y \} \mid y \in range(g_i) \}. $

Sanity check: it should be clear that $P_0 = \{ \{x\} \mid x \in \{0, 1\}^n \}$ and that $P_d = f^{-1}(range(f))$.

We say that equivalence relation $P$ refines equivalence relation $Q$ when $\forall p \in P, \exists q \in Q, p \subseteq q$. We denote this by $P \leq Q$. Given the setup above, it is not hard to show that

$\forall i \in \{1 \cdots d\}, P_{i-1} \leq P_i.$

My question is: Does there exist a basis $B$ such that for all $f$, $C \in \mathcal{C}(f)$, $P_{i-1} \neq P_i$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.