7
$\begingroup$

I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this type is a circuit $C_s$ defined over a beginning subset of $\mathbb{N}$ (i.e., $\{0,...,n\}$) containing only $\{\cap,\cup\}$ gates. My question is how efficiently can a boolean circuit $C_b$ be constructed that computes the same output as $C_s$ and whether there exists a lower bound on the size of such a $C_b$.

The simplest way I can think of, in order to achieve the above, would be to represent a set $S$ by a binary array $\mathbf{s} = s_1,...,s_n$ of size $n$ where a 1 in position $i$ would signify that element $i \in S$. With this representation in mind, a union operation between sets $S,P$ can be implemented by $n$ OR gates by performing a point-wise OR for arrays $\mathbf{s}$ and $\mathbf{p}$. Likewise, intersection would be captured by point-wise AND. This approach would imply that $|C_b| \in O(n)$ and likewise for the reduction time (with a multiplicative factor of $|C_s|$).

Can someone point out whether this approach is optimal or whether there is a better way to achieve the above? More importantly, is there a known lower bound for transformation of circuits over sets of naturals to boolean circuits? My research is security-motivated and the problem is governed by a security parameter $\lambda$ such that $n \in O(2^{\lambda})$ hence my approach is infeasible as it yields exponential size $C_b$. (EDIT: Assume each set $S$ is of size only $O(poly(\lambda)$)

$\endgroup$
2
$\begingroup$

A simple conversion process for $\boldsymbol\cup\,$, $\boldsymbol\cap\,$, constants, and complements

Note that any integer-set circuit representing a set $S \subseteq \{0,1,\ldots,N-1\}$ can be represented by a boolean circuit which tests $x \mathbin{\in?} S$ for $0 \leqslant x < N$. If $N = 2^n$, this is a boolean circuit with $n$ inputs. We may construct such a circuit $C_n$ as follows. $\def\GE#1{\mathrm{GE#1}}\def\PRIME={\mathrm{PRIME}}$

  1. Using AND, OR, and NOT gates, we can very easily simulate equality of the input with a binary representation of any integer $0 \leqslant x < 2^n$ with a circuit of size $n$ and depth $\log (n)$.

  2. Next, we may represent your input sets as also being constructed by $\cup$ circuits, constructed from singletons $\{x\}$ for $1 \leqslant x < N$. If $S_j$ has size $m_j \leqslant M$, this requires a circuit with a boolean tree structure, with $m-1$ union gates, having depth at most $\log(m)$.

  3. Finally, we may represent unions and intersections of your sets $S_j$ by logical ANDs and ORs of membership in the input sets. This part of the circuit has the same size $s$ and depth $d$ as the depth of your integer-set-circuit.

We may then obtain a boolean circuit $C_n$ of depth at most $d + \log m + \log n$ and size at most $s + m + mn$. The complexity of building this circuit is essentially $O(s + m(\log m + n \log n))$, arising from doing the necessary construction of the binary trees for the gates representing each $S_j$ and $\{x\}$ for $x \in S_j$.

Note that the complexity does not increase at all if you allow logical complementation, which would represent in principle an infinitely large set including numbers larger than the input size; though to represent numbers which are $N$ or larger, we must use uniform circuit families $\{C_n\}$ rather than a single circuit $C_n$. The construction above will build these efficiently, however.

Remarks on the power of integer-set circuits with arithmetic

In the (extremely powerful!) model of arithmetic circuits including $+$ and $\times$ gates, this construction fails because the outputs to those gates implicitly involve existential quantifiers over satisfying inputs to subcircuits of arbitrary size. As your linked article notes, the Goldbach conjecture can be tested by evaluating $G(0)$, where $G$ is a (finite depth!) circuit, $$ G :=\overline{\{0\} \times \Bigl(\bigl[ \{2\} \times \GE2 \bigr] \cap \bigl[\; \overline{\PRIME + \PRIME}\;\bigr]\Bigr)} \;, $$ where $\GE2 := \overline{\{0\} \cup \{1\}}$ tests whether an input is $\geqslant 2$, and $\PRIME := \GE2 \cap \bigl[\,\overline{\GE2 \times \GE2}\,\bigr]$ tests whether an input is prime. The enormous power of these circuits seem to me to come from combining negation (which allows you to obtain infinite sets from finite ones) with the $+$ and $\times$ gates (which allow existential quantification over all inputs to sub-circuits, as to whether there are accepted inputs whose sum or product is equal to the input integer). If you do not have additions or multiplications, those quantifications are absent, and the problem becomes much simpler — indeed, very close in flavour to a run-of-the-mill boolean circuit.

$\endgroup$
  • $\begingroup$ I am afraid I am missing a point here. Are you assuming that the circuit $S$ contains $\{i\}$-type gates in order to construct each input set before doing set operations on them? If I assume that all involved sets are of size $m$ and $p$ such sets are used then $|S| \in O(mp)$. Also when converting to a boolean circuit, shouldn't each $\{i\}$-type gate be represented by at least $k$ boolean gates? $\endgroup$ – Jonathan Naysmith Mar 31 '13 at 1:06
  • $\begingroup$ @JonathanNaysmith:I have attempted to clarify my construction, and have fixed some minor errors. $\endgroup$ – Niel de Beaudrap Apr 1 '13 at 15:57
0
$\begingroup$

Let the size of each input set $|S| \leq m = f(\lambda)$ and let $k$ be the number of inputs.

With corresponding input set $S$ let $L = S_1, ..., S_{|S|}, \emptyset_{|S|+1}, ..., \emptyset_m$ and let $\mathbf{L}$ be the concatenation of all $L$.

Let $\mathbf{s}$ be a binary array of length $mk$ where $\mathbf{s}_i$ is $1$ if $S$ contains an element that first occurs in $\mathbf{L}$ at position $i$.

We can construct $\mathbf{s}$ from $S$ and $\mathbf{L}$ using $O(m^2k)$ integer comparators or $O(m^2k^2)$ comparators for all $S$. Representing elements of $S$ in base 2, comparators can be constructed using $O(\lambda)$ boolean gates.

Now $C_s$ can be transformed as you describe with each gate in $C_s$ being implemented by $mk$ gates in $C_b$.

An output $S_{out}$ can be constructed from a boolean array $\mathbf{s}_{out}$ by comparison with $\mathbf{L}$ using $O(mk)$ integer gates. To match output and input formats you can build an odd-even mergesort comparator network with $O(mk~log^2(mk))$ integer comparators per output.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.