Classifying Functions with Exact Synthesis

Winston Haaswijk Eleonora Testa Mathias Soeken Giovanni De Micheli

Integrated Systems Laboratory, EPFL, Lausanne, VD, Switzerland

Abstract—Due to recent advances, constraint solvers have TABLE I

become efficient tools for synthesizing optimum Boolean circuits. C OMBINATIONAL COMPLEXITY OF ALL 4- INPUT FUNCTIONS USING
We take advantage of this by showing how SAT based exact 2- INPUT OPERATORS [1]
synthesis may be used as a method for finding minimum length
Boolean chains. As opposed to other exact synthesis methods, C(f ) Classes Functions
ours may be easily parallelized, which we use to obtain a speedup 0 2 10
of approximately 48 times. By combining our method with NPN 1 2 60
canonization, we find for the first time the minimum length 2 5 456
chains for all 4- and 5-input functions in terms of 3-input 3 20 2474
Boolean operators. Finally, we propose a hardware acceleration 4 34 10624
method for NPN canonization. It can be used to speed up NPN 5 75 24184
canonization in existing algorithms, and we believe it will allow 6 72 25008
us to find all 6-input NPN classes as well. 7 12 2720

I. I NTRODUCTION
TABLE II
Every n-input Boolean function f over inputs x1 , . . . , xn C OMBINATIONAL COMPLEXITY OF ALL 5- INPUT FUNCTIONS USING
can be expressed in terms of a Boolean chain. Such a chain 2- INPUT OPERATORS [1]
is a sequence of steps that combine previous steps or inputs
using Boolean operators from a set of primitives P . In the C(f ) Classes Functions
context of digital design it is typical to refer to a Boolean 0 2 12
1 2 100
chain and steps as a logic network and gates, respectively. 2 5 1140
But as we are considering some fundamental properties of 3 20 11570
Boolean functions, we avoid using such hardware jargon. The 4 93 109826
5 389 995240
minimum length of a Boolean chain to compute f is referred 6 1988 8430800
to as combinational complexity of f , and denoted C(f ) [1]. 7 11382 63401728
More formally, a Boolean chain for corresponding to function 8 60713 383877392
9 221541 1519125536
of n inputs is a sequence (xn+1 , . . . , xn+r ), where 10 293455 2123645248
11 26535 195366784
xi = gi (x1(i) , x2(i) , . . . , xm(i) ) for n + 1 ≤ i ≤ n + r. 12 1 1920
In other words, each step in the chain combines m previous
steps or inputs with x1(i) < x2(i) < · · · < xm(i) < xi using the
m-input Boolean operator gi . Note that this definition allows chains has applications in logic synthesis and optimization. For
for multiple fanouts: multiple distinct steps in the chain may example, logic rewriting algorithms optimize logic networks
refer to the same input or step xj . by replacing subnetworks by optimized Boolean chains [8],
There are several research directions that address questions [10].
about combinational complexity in different ways. We may Knuth [1] has computed the combinational complexity of
consider these directions as consisting of three different all 4- and 5-input Boolean functions composed of all 2-input
categories. The first category is concerned with finding set Boolean operators. In this work we repeat the experiment
of primitives such that the complexity of all Boolean functions by using all 3-input Boolean operators as set of primitives.
f satisfies some upper bound (see, e.g., [2]–[4]). The second is Following Knuth we make use of the property that all functions
concerned with finding complex Boolean functions that satisfy that are equivalent up to input negation, input permutation,
a lower bound for some given set of primitives (see, e.g., [5]– and output negation (NPN equivalence, [11]) have the same
[7]). Finally, the third is concerned with finding exact numbers combinational complexity. This allows us to consider a subset of
for the combinational complexity given a subset of Boolean 222 and 616,126 functions instead of 65,536 and 4,294,967,296
functions and a set of primitives P (see, e.g., [1], [8], [9]). functions for 4 and 5 inputs, respectively.
The work we present in this paper falls into the third category. In fact, the exact numbers for the combinational complexity
Having exact numbers for the combinational complexity of for all 222 NPN classes of the 4-input functions can be found
some small functions can help to find tighter upper bounds efficiently by enumerating all Boolean chains until some chain
for larger functions by using arguments from Boolean decom- for each function has been encountered [1]. Table I lists the
position. Further, efficient methods for finding small Boolean combinational complexity for all 4-input functions. A more
 a a a a

b b b b
(a) (b) c c
Fig. 1. An example of two different functions that are P-equivalent. The (a) (b)
circuit in (a) computes f = a · b̄ and the circuit in (b) computes g = ā · b.
They can be made equivalent by swapping the inputs to the AND gate. Fig. 2. An example of two different functions that are NPN-equivalent.
The circuit in (a) computes h = a · b + c and the circuit in (b) computes
i = ā · c̄ + b̄ · c̄. They are NPN-equivalent because circuit (a) can be made
equivalent to circuit (b) by inverting its output.
sophisticated algorithm is required to find exact numbers for
the combinational complexity for all 616,126 NPN classes of
TABLE III
the 5-input functions. Yet, “thanks to a bit of good luck” (as C OMPARING THE NUMBER OF n- INPUT FUNCTIONS AND NPN CLASSES
stated in [1]) and the computer program BOOLCHAINS,1 it was
possible to find the numbers presented in Table II. However, n Number of functions Number of NPN classes
modifications to the main algorithm were required to find the 0 1 1
numbers for some of these classes. Certain classes were handled 1 4 2
2 16 4
as special cases. The vast majority of computation time was 3 256 14
spent finding the 11-step chains for their 6 corresponding NPN 4 65,536 222
classes and the 12-step chain for its single corresponding NPN 5 4,294,967,296 616,126
6 18,446,744,073,709,551,616 200,253,952,527,184
class [1].
We propose the use of SAT based exact synthesis to find
the combinational complexity of all 4- and 5-input functions,
and show that it is an efficient method for doing so. Exact [f ]), we say that they are NPN-equivalent. We pick one function
ˆ
synthesis [12]–[14] is a method that, given a set of primitives, f ∈ [f ] to be the equivalence class representative. We say that
ˆ
finds optimum Boolean chains. We adjust the typical exact f is the canonical representative of [f ]. Typically, the function
synthesis formulation by considering 3-input Boolean operators f ∈ [f ] whose truth table corresponds the smallest integer
as the set of primitives. Our findings are that exact synthesis can value is chosen to be the equivalence class representative.
efficiently find optimum Boolean chains for all 4- and 5-input In general, Boolean function classification is useful when
NPN classes. It does so without the requirement to explicitly we want to learn something about all functions. For example,
enumerating all Boolean chains or to use any case distinctions. in this paper we are interested in finding the minimum length
Further, our method does not require any modifications to Boolean chain for all 5-input functions. Since NPN equivalence
handle special cases. Finally, our method is easily parallelized. relies only on permutations and negations, it does not affect the
length of Boolean chains. The minimum length Boolean chain
II. P RELIMINARIES for any f ∈ [f ] can be derived from chain for fˆ, simply by
A. NPN Canonization applying the proper permutations and negations. More formally,
Two functions are P-equivalent if they are equivalent up to C(f ) = C(g) if g ∈ [f ]. Hence, to find C(f ) for all n-input
permutation of their inputs. For example the functions f = a · b̄ functions we do not need to examine all functions. Instead we
ˆ
and g = ā·b are P-equivalent, since we can make them equal by can find C(f ) only for the NPN class representatives. This is
swapping the inputs a and b (see Figure 1). NPN equivalence preferable, since the number of NPN classes is significantly
is a generalization of P equivalence. We say that two functions smaller than the number of functions. Table III lists the number
are NPN-equivalent if they are equivalent up to permutation of of functions and classes for up to 6 inputs to illustrate how
their inputs and negation of their inputs and output [15], [16]. significant this difference is. NPN classification has applications
For example, the functions h = a · b + c and i = ā · c̄ + b̄ · c̄ ranging from Boolean matching to logic rewriting and exact
are NPN-equivalent, since h can be made equivalent to i by synthesis [17]–[19]. Efficient exact and heuristic algorithms for
negating its output (see Figure 2). NPN classification have been developed over the years [17],
The number of single output n-input functions is 2 . This [20], [21].
2n

number grows rapidly as we increase n. NPN canonization is a B. Exact Synthesis

way to group Boolean functions into classes that are equivalent
up to permutation and negation of inputs and output. Due to Given a set of primitives P , an exact synthesis algorithm
this grouping into classes we use the terms NPN canonization finds the optimum representation for a Boolean function in
and NPN classification interchangeably. We can view an NPN terms of P . Given different objectives, different representations
equivalence class as a set of functions [f ]. When two functions may be considered optimum. For example, we may be looking
f and g are part of the same NPN class (i.e., f ∈ [f ] and g ∈ for the representation with the smallest depth, or for the smallest
possible Boolean chain. For example, suppose that P consists
1 http://www-cs-faculty.stanford.edu/˜uno/programs/boolchains.tgz only of the 2-input NAND operator. We could then use exact
synthesis to find the smallest possible chain of NAND operators Since all elements in [f ] are visited when computing fˆ, we
that implements a given function. can store this information while enumerating all representatives
Exact synthesis is a special case of the well-known mini- of all NPN5 classes. In the case n = 5, which we consider,
mum circuit size problem (MCSP) [22]. No polynomial time there are 22 = 4, 294, 967, 296 single output 5-input functions.
algorithm for either MCSP or exact synthesis is known, and We initialize a map R that5 is indexed by 5-input functions
they are conjectured to be computationally intractable [23]. and initialize each of its 22 elements with Λ (null). In a loop
Due to its complexity, the application of exact synthesis has we find some f for which R(f ) = Λ, and compute fˆ using
been limited to small functions, i.e., functions of 4 or 5 inputs. the algorithm described above. While visiting all elements f 0
There are various ways in which we can implement an in [f ] we set R(f ) ← fˆ. Obviously, this loop needs to be
exact synthesis algorithm [8], [13], [24]. Recently, a class traversed only 616,126 times, the number of NPN classes for
of implementations that view exact synthesis as a SAT/SMT 5-input functions. Afterwards, the image of R is the set of all
problem has been getting more attention. We describe how representatives.
the problem may be formulated in such a way that it can be
B. Finding Minimum Length Chains With Exact Synthesis
solved by a SAT/SMT solver. Suppose that we are given the
set of primitives P and the Boolean function f . Our goal is After finding the NPN classes, we use exact synthesis to
to find the smallest possible Boolean chain that computes f find the minimum length Boolean chains. We use a SAT based
in terms of P . Let us assume that our constraint solver has a method similar to the one introduced in Section II-B. Our
procedure solution exists(f, g) which returns true if and only algorithm is an extension of the SAT formulation proposed by
if there exists a Boolean chain of g operators from P that Knuth in [12]. This formulation is itself based on earlier work
computes f . Our goal then reduces to finding the minimum g from Kojevinok et al. [13] and Eén [14]. To find all minimum
for which this is true. We start by setting g ← 0, and checking length chains, we simply apply our exact synthesis to every 4-
if solution exists(f, g) is true. If not, we increment g and and 5-input NPN class.
try again until we find a value for g that works. The first g A key difference between our synthesis algorithm and
for which solution exists(f, g) returns SAT is the minimum. previous approaches is that our set of primitives P consists of
The procedure solution exists(f, g) can be expressed as a all 3-input Boolean operators. By contrast, in earlier approaches
SAT or SMT formula. Hence, we can solve the exact synthesis P typically consist of 2-input operators, or a small subset of 2-
problem with a SAT or SMT solver. Other optimization criteria, and 3-input operators [8], [9], [12]. The use of 3-input operators
such finding the Boolean chain with minimum depth, can be significantly speeds up synthesis time. We are not aware of
achieved similarly. any other exact synthesis algorithm that is able to find these
minimum length Boolean chains, at least not without handling
III. E XACT S YNTHESIS M ETHOD special cases differently. Moreover, using 3-input operators
leads to novel results: the minimum length chains in terms of
Our goal in this paper is to find the minimum length Boolean 2-input operators are known, but the minimum chains in terms
chains for all 4- and 5-input functions in terms of 3-input of 3-input operators are not.
Boolean operators. In other words, P consists of all 3-input Another difference between our method and others is that
Boolean functions. We present a method that achieves this goal ours is easily parallelized. Exact synthesis may be invoked
by using NPN classification and exact synthesis. Roughly, our in parallel on every NPN class we find, as there are no
method can be divided into two parts: (i) finding all 5-input dependencies between invocations. Other methods would be
NPN classes, and (ii) using exact synthesis to find all minimum significantly harder to parallelize. For example, enumeration
length Boolean chains. based methods work by doing a search of different circuit
structures [1]. This search proceeds sequentially, yielding a
A. Finding All NPN Classes
sequence of optimum chains. This is not a process that is trivial
In order to find the representative fˆ for a given function to parallelize, as lower parts of the search space tree depend
f , one needs to visit all functions in [f ] to find the smallest on choices made above.
one. If f has no helpful properties—such as symmetries in the For both 4-input and 5-input functions we can find tight
inputs (see, e.g., [20], [25])—one needs to apply all possible upper bounds on the length of minimum Boolean chains. Our
combinations of 2n input negations and n! input permutations set of primitives P includes the 2-to-1 multiplexer, as it has
for both f and f¯. In order to reduce the effort, we can use a a corresponding 3-input Boolean operator. We can use this
smart ordering in which all these transformations are applied. operator to efficiently decompose functions and to find an upper
We can use gray code enumeration to invert inputs, thereby bound. For example, we can write any 4-input Boolean function
flipping only one bit at a time. In a similar way we can use as f (x1 , x2 , x3 , x4 ) = x̄1 ·f (0, x2 , x3 , x4 )+x1 ·f (1, x2 , x3 , x4 ).
plain changes (see, e.g., [26]) to visit all permutations by This is known as Boole’s expansion, and can be implemented
swapping two adjacent inputs at each time. Note that it is by a 2-to-1 multiplexer. Note that the cofactors of f are 3-input
possible to combine both concept in an enumeration algorithm functions. This means that they can both be implemented by
that visits all signed permutations, i.e., permutations in which a single operator from P . Figure 3 shows a sketch of this
elements can be complemented [1]. decomposition. Therefore, by using a multiplexer to do the
 f TABLE V
C OMBINATIONAL COMPLEXITY OF ALL 5- INPUT FUNCTIONS USING
3- INPUT OPERATORS
0 1
x1
Computation time (sec)
fx̄1 fx 1 C(f ) Classes Functions Avg. Max. Total
0 2 12 0.000 0.000 0.000
x2 x3 x4 x2 x3 x4 1 12 2,280 0.001 0.002 0.017
2 311 395,676 0.003 0.005 0.911
Fig. 3. We can implement any 4-input Boolean function by using at most 3 12,257 58,519,472 0.021 0.089 260.550
three 3-input operators. 4 339,739 2,321,397,216 1.805 57.898 613,082.000
5 263,805 1,914,652,640 18.550 3,261.770 4,893,600.000

TABLE IV
C OMBINATIONAL COMPLEXITY OF ALL 4- INPUT FUNCTIONS USING
3- INPUT OPERATORS As shown by Table V, exact synthesis turns out to be an
efficient method for finding the minimum chains. No function
Computation time (sec) requires more than an hour to be synthesized, and the average
C(f ) Classes Functions Avg. Max. Total
synthesis time is just 8.938 seconds. This means that our
0 2 10 0.000 0.000 0.000 method is able to find all minimum length chains, without
1 12 932 0.001 0.002 0.014
2 117 34,250 0.001 0.002 0.173 having to resort to different handling of special cases.
3 91 30,344 0.003 0.005 0.245 Despite the efficiency of our method, the total sequential
CPU time necessary to find all minimum length chains is
still 8.938 × 616, 126 = 5, 506, 943.478 seconds, simply
initial expansion and two operators to implement the cofactors, due to the large number of functions. However, one useful
we can implement any 4-input function with at most 3 operators property of our method is that it can be easily parallelized. By
from P . A similar argument can be used to show that we can running it on 48 threads in parallel the total wall clock time
implement any 5-input function using at most 7 operators. reduces significantly. We are able to synthesize all functions
in 5,506,943.478
48 = 114727.99 seconds. As there are 86,400
C. Experimental Results seconds in a day, this allows us to complete synthesis in just
114,727.99
86,400 = 1.3 days. In other words, we are able to take full
Using NPN classification reduces the number exact invo- advantage of the embarrassingly parallel nature of the problem,
cations. However, at 616,126 5-input classes the number is and to obtain a speedup of approximately 48 times. Other
still large. To make the run time of our experiment practical exact synthesis methods, such as those based on exhaustive
we run exact synthesis in parallel. We use a machine with 2 enumeration of Boolean chains, are much harder to parallelize.
Intel Xeon E5-2680 v3 (Haswell) CPUs, each of which has Therefore, even if we suppose they have better run time per
12 cores with support for 2 hyperthreads. Since the problem is function, they may still not be as practical as our method.
embarrassingly parallel, we take full advantage of our hardware
by using 48 threads.
IV. C ONCLUSIONS AND O UTLOOK
We first use our method to find the minimum length Boolean
chains for all 4-input operators. The results of this can be We present a method for finding the minimum length
found in Table IV. This table shows the number of NPN Boolean chains for all 4- and 5-input functions in terms of
classes that have a specific combinational complexity C(f ), 3-input operators. Our method is based on NPN classification
as well as the corresponding number of functions with that and exact synthesis. It can also be easily parallelized, enabling
complexity. Further, it shows run time information. For each an approximate 48× reduction in run time. We show that our
value of C(f ) we show the average, maximum, and total exact synthesis implementation is efficient and able to find all
synthesis run time (in seconds) for all the NPN classes with that minimum length chains without needing to handling any special
combinational complexity. The results show that our synthesis cases differently. For the first time, we present the lengths of
algorithm is efficient: it never requires more than 0.005 seconds these minimum chains as well as their implementations.
to synthesize any 4-input function. Besides being of academic interest, finding minimum chains
The results also show that the upper bound we derived for has practical application. For example, they can be used
4-input functions in Section III-B is exact. There are exactly in logic optimization and technology mapping. It is also
91 NPN classes, corresponding to 30344 functions, that cannot motivated by emerging and existing technologies. In recent
be implemented by using fewer than 3 operators. years different nanotechnologies have been implementing more
Next, we apply our method to finding the minimum length powerful devices that go beyond the capabilities of traditional
chains for all 5-input functions. The results can be found NAND/NOR gates [27]–[29]. These devices implement more
in Table V. Interestingly, the upper bound we found in expressive operators, such as 3-input majority or minority
Section III-B was not exact in this case. Any 5-input function functions. More traditionally, gates such as multiplexers also
can be implemented by using at most 5 3-input operators. correspond to 3-input operators. Hence, finding optimum chains
 f [63 : 0] [4] W. Hesse, E. Allender, and D. A. M. Barrington, “Uniform constant-depth
threshold circuits for division and iterated multiplication,” J. Comput.
Syst. Sci., vol. 65, no. 4, pp. 695–716, 2002.
[5] N. Blum, “A Boolean function requiring 3n network size,” Theor. Comput.
NPN class (All permutations) Sci., vol. 28, pp. 337–345, 1984.
[6] W. J. Paul, “A 2.5n-lower bound on the combinational complexity of
Boolean functions,” SIAM J. Comput., vol. 6, no. 3, pp. 427–443, 1977.
... [7] C. Schnorr, “The combinational complexity of equivalence,” Theor.
Comput. Sci., vol. 1, no. 4, pp. 289–295, 1976.
f1 f2 f92,160 [8] M. Soeken, L. G. Amarù, P. Gaillardon, and G. De Micheli, “Optimizing
majority-inverter graphs with functional hashing,” in Design, Automation
Find representative and Test in Europe, 2016, pp. 1030–1035.
[9] R. Schroeppel, “A few mathematical experiments,”
talk at Experimental Mathematics Workshop, slides at
http://richard.schroeppel.name:8015/expmath04-schroeppel-talk.pdf.
fˆ[63 : 0] [10] W. Haaswijk, M. Soeken, L. Amarú, P.-E. Gaillardon, and G. De Micheli,
“A Novel Basis for Logic Rewriting,” in ASPDAC, 2017.
[11] E. Goto and H. Takahasi, “Some theorems useful in threshold logic
Fig. 4. NPN classification circuit for enumerating Boolean functions,” in International Federation for
Information Processing Congress, 1962, pp. 747–752.
[12] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 6:
based on 3-input operators can help in the design of circuits Satisfiability. Reading, Massachusetts: Addison-Wesley, 2015.
[13] A. Kojevnikov, A. S. Kulikov, and G. Yaroslavtsev, “Finding efficient
based on these technologies. circuits using sat-solvers,” in Theory and Applications of Satisfiability
Classifying 6-input functions—an outlook: The classification Testing, 2009, pp. 32–44.
results for 4- and 5-input functions are a self-contained result [14] N. Eén, “Practical SAT - a tutorial on applied satisfiability solving,” in
FMCAD, 2007.
and very helpful both in theory and practice. But what if we’d [15] M. Harrison, “The Number of Equivalence Classes of Boolean Functions
like to go a step further and investigate the combinational Under Groups Containing Negation,” Electronic Computers, IEEE
complexity of all 6-input functions? There exist more than 200 Transactions on, vol. 12, pp. 559–561, 1963.
[16] S. L. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital
trillion NPN classes and to compute them requires a lot of Logic. Academic Press, 1985.
time making our classification approach infeasible. We suggest [17] Z. Huang, L. Wang, Y. Nasikovskiy, and A. Mishchenko, “Fast
to investigate whether hardware acceleration can be a solution Boolean matching based on NPN classification,” in Int’l Conf. on Field-
Programmable Technology, 2013, pp. 310–313.
to overcome this limitation and compute NPN classes using [18] A. Mishchenko, S. Chatterjee, and R. K. Brayton, “DAG-aware AIG
dedicated hardware. Such hardware can exploit full parallelism rewriting a fresh look at combinational logic synthesis,” in Design
in computing the NPN representative as shown by the design Automation Conference, 2006, pp. 532–535.
[19] W. Haaswijk, M. Soeken, L. Amarú, P.-E. Gaillardon, and G. De Micheli,
in Fig. 4. Input to the circuit is a function f and output its “LUT Mapping and Optimization for Majority-Inverter Graphs,” in IWLS,
representative fˆ. Both functions are represented as 64-bits 2016.
vectors. The circuit consists of one block to enumerate all [20] A. Petkovska, M. Soeken, G. De Micheli, P. Ienne, and A. Mishchenko,
“Fast Hierarchical NPN Classification,” in Field Programmable Logic
NPN classes and one block to calculate the representative and Applications, 2016, pp. 1–4.
given all elements in the class. [21] M. Soeken, A. Mishchenko, A. Petkovska, B. Sterin, P. Ienne, R. K.
Input to the first block is the 6-input function f . This block Brayton, and G. De Micheli, “Heuristic NPN Classification for Large
Functions Using AIGs and LEXSAT Mathias,” in International Con-
considers all 26 · 6! = 46, 080 permutations for f , given by ference on Theory and Applications of Satisfiability Testing, 2016, pp.
permuting and negating inputs. At the circuit level, both these 212–227.
operations on inputs result in considering different orders for the [22] V. Kabanets and J.-Y. Cai, “Circuit minimization problem,” Proceedings
of the thirty-second annual ACM symposium on Theory of computing -
64 bits of f . The same 46, 080 permutations are considered for STOC ’00, pp. 73–79, 2000.
f¯. Hence, the first block has 92, 160 64-bit outputs representing [23] C. D. Murray and R. R. Williams, “On the (non) np-hardness of com-
all functions in [f ]. The second block finds the minimum of puting circuit complexity,” in Conference on Computational Complexity,
vol. 30, 2015, pp. 365–380.
all these functions by a balanced tree of comparators, resulting [24] E. Lawler, “An approach to multilevel boolean minimization,” Journal
in dlog2 92, 160e = 17 levels. The output of this comparator of the ACM, vol. 11, no. 3, pp. 283–295, 1964.
tree is the smallest functions, i.e., the representative fˆ. [25] A. Abdollahi and M. Pedram, “A new canonical form for fast Boolean
matching in logic synthesis and verification,” in Design Automation
ACKNOWLEDGMENTS Conference, 2005, pp. 379–384.
[26] E. Morris, The history and art of change ringing. Chapman & Hall,
This research was supported by H2020-ERC-2014-ADG 1931.
669354 CyberCare and the Swiss National Science Foundation [27] P. D. Tougaw and C. S. Lent, “Logic devices implemented using quantum
cellular automata,” Journal of Applied Physics, vol. 75, no. 3, 1994.
(200021-169084 MAJesty). [28] D. Lee, W. S. Lee, C. Chen, F. Fallah, J. Provine, S. Chong, J. Watkins,
R. T. Howe, H. S. P. Wong, and S. Mitra, “Combinational logic design
R EFERENCES using six-terminal nem relays,” IEEE Transactions on Computer-Aided
[1] D. E. Knuth, The Art of Computer Programming. Upper Saddle River, Design of Integrated Circuits and Systems, vol. 32, no. 5, pp. 653–666,
New Jersey: Addison-Wesley, 2011, vol. 4A. 2013.
[2] M. L. Furst, J. B. Saxe, and M. Sipser, “Parity, circuits, and the [29] M. De Marchi, D. Sacchetto, J. Zhang, S. Frache, P.-E. Gaillardon,
polynomial-time hierarchy,” Mathematical Systems Theory, vol. 17, no. 1, Y. Leblebici, and G. De Micheli, “Top–down fabrication of gate-all-
pp. 13–27, 1984. around vertically stacked silicon nanowire fets with controllable polarity,”
[3] J. Håstad, “Almost optimal lower bounds for small depth circuits,” in IEEE Transactions on Nanotechnology, vol. 13, no. 6, pp. 1029–1038,
Annual ACM Symposium on Theory of Computing, 1986, pp. 6–20. 2014.