The complexity of the parity function in unbounded fan-in, unbounded depth circuits. (English) Zbl 0749.94025

An involved study of the complexity of the parity function \(f_ n\) of \(n\) variables realised by unbounded fan-in Boolean circuits is presented. The number of gates of a circuit is considered as the main complexity measure, but the number of wires is also investigated in some cases. Several optimal and almost optimal (lower and upper) bounds on the complexity of \(f_ n\) for distinct bases are established. The proof techniques used include several nice ideas, and are interesting for everybody working in Boolean function complexity theory.


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Chandra, A.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. comput., 13, 423-439, (1984) · Zbl 0538.68038
[2] Hajnal, A.; Maass, W.; Pudlák, P.; Szegedy, M.; Turán, G., Threshold circuits of bounded depth, Proc. 28th ann. symp. on foundations of computer science, 99-110, (1987)
[3] Hastad, J., Almost optimal lower bounds for small depth circuits, Proc. 18th ann. ACM symp. on theory of computing, 6-20, (1986)
[4] Lai, H.C., A study of current logic design problems, ()
[5] Lai, H.C.; Muroga, S., Logic networks with a minimum number of NOR (NAND) gates for parity functions of n variables, IEEE trans. comput., 36, 157-166, (1987) · Zbl 0606.94014
[6] Muroga, S., VLSI system design, (1982), Wiley New York
[7] Nakagawa, T.T.; Lai, H.C., Reference manual of FORTRAN program ILLOD-(NOR-B) for optimal NOR networks — revised, ()
[8] Nakagawa, T.T.; Lai, H.C.; Muroga, S., Design algorithm of optimal NOR networks by the branch-and-bound approach, ()
[9] Parberry, I.; Schnitger, G., Parallel computation with threshold functions, (), 272-290
[10] Redkin, N.P., Proof of minimality of circuits consisting of functional elements, Systems theory research, 23, 85-103, (1973) · Zbl 1194.94210
[11] Reif, J., On threshold circuits and polynomial computation, Proc. 2nd conf. on structure in complexity theory, 118-123, (1987)
[12] Schnorr, C.P., Zwei lineare untere schranken für die komplexität boolescher funktionen, Computing, 13, 155-171, (1974) · Zbl 0313.68033
[13] Wegener, I., The range of new lower bound techniques for WRAMs and bounded depth circuits, Inform. process. cybernet., 23, 537-543, (1987) · Zbl 0641.68065
[14] Wegener, I., The complexity of Boolean functions, (1987), Teubner, Stuttgart/Wiley Chichester, Wiley-Teubner Series in Computer Science · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.