research-article

Open access

On the Complexity of Hazard-free Circuits

Authors:

Christian Ikenmeyer,

Balagopal Komarath,

Christoph Lenzen,

Vladimir Lysikov,

Karteek SreenivasaiahAuthors Info & Claims

Journal of the ACM (JACM), Volume 66, Issue 4

Article No.: 25, Pages 1 - 20

https://doi.org/10.1145/3320123

Published: 23 August 2019 Publication History

All formats PDF

Abstract

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards.

These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions.

As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement.

As a side result, we establish the NP-completeness of several hazard detection problems.

References

[1]

Miklos Ajtai and Yuri Gurevich. 1987. Monotone versus positive. J. ACM 34, 4 (Oct. 1987), 1004--1015.

Digital Library

[2]

Noga Alon and Ravi B. Boppana. 1987. The monotone circuit complexity of Boolean functions. Combinatorica 7, 1 (1987), 1--22.

Digital Library

[3]

Walter Baur and Volker Strassen. 1983. The complexity of partial derivatives. Theor. Comput. Sci. 22 (1983), 317--330.

[4]

Norbert Blum. 1985. An Ω (n<sup>4/3</sup>) lower bound on the monotone network complexity of the nth degree convolution. Theoretical Computer Science 36, Supplement C (1985), 59--69.

[5]

J. Brzozowski, Z. Esik, and Y. Iland. 2001. Algebras for hazard detection. In Proceedings of the 31st International Symposium on Multiple-Valued Logic.

Digital Library

[6]

J. A. Brzozowski. 1999. Some applications of ternary algebras. Publicationes Mathematicae (Debrecen) 54, Supplement (1999), 583--599.

[7]

Janusz A. Brzozowski and Carl-Johan H. Seger. 1995. Asynchronous Circuits. Springer, New York.

[8]

H. Martin Bücker and George F. Corliss. 2006. A bibliography of automatic differentiation. In Automatic Differentiation: Applications, Theory, and Implementations, Martin Bücker, George Corliss, Uwe Naumann, Paul Hovland, and Boyana Norris (Eds.). Springer-Verlag, Berlin, 321--322.

[9]

Samuel H. Caldwell. 1958. Switching Circuits and Logical Design. John Wiley 8 Sons.

[10]

Ashok K. Chandra and George Markowsky. 1978. On the number of prime implicants. Discrete Math. 24, 1 (1978), 7--11.

Digital Library

[11]

Marc Davio, Jean-Pierre Deschamps, and André Thaysé. 1978. Discrete and Switching Functions. McGraw-Hill.

[12]

A. Martín del Rey, G. Rodríguez Sánchez, and A. de la Villa Cuenca. 2012. On the Boolean partial derivatives and their composition. Appl. Math. Lett. 25, 4 (2012), 739--744.

[13]

E. B. Eichelberger. 1965. Hazard detection in combinational and sequential switching circuits. IBM J. Res. Dev. 9, 2 (March 1965), 90--99.

Digital Library

[14]

Herbert B. Enderton. 2001. A Mathematical Introduction to Logic (2nd ed.). Academic Press.

[15]

Stephan Friedrichs. 2017. Metastability-containing circuits, parallel distance problems, and terrain guarding. Ph.D. Dissertation. Universität des Saarlandes, Postfach 151141, 66041 Saarbrücken. http://scidok.sulb.uni-saarland.de/volltexte/2017/6966

[16]

Stephan Friedrichs, Matthias Függer, and Christoph Lenzen. 2018. Metastability-containing circuits. IEEE Trans. Comput. (2018). Retrieved from https://arxiv.org/abs/1606.06570.

[17]

M. Goto. 1948. Application of three-valued logic to construct the theory of relay networks (in Japanese) 三値論理学の継電器回路網理論への應用 . Proceedings of the Joint Meeting IEE, IECE, and I. of Illum. E. of Japan, 電気三学会東京支部連合大会講演要旨. 昭和 22 · 23年 (1948), 31--32.

[18]

M. Goto. 1949. Application of logical mathematics to the theory of relay networks (in Japanese). J. Inst. Elec. Eng. Japan 64, 726 (1949), 125--130.

[19]

Michelangelo Grigni and Michael Sipser. 1992. Monotone complexity. In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity. Cambridge University Press, New York, NY, 57--75. http://dl.acm.org/citation.cfm?id=167687.167706

Digital Library

[20]

W. Hu, J. Oberg, A. Irturk, M. Tiwari, T. Sherwood, D. Mu, and R. Kastner. 2012. On the complexity of generating gate level information flow tracking logic. IEEE Trans. Info. Forensics Secur. 7, 3 (June 2012), 1067--1080.

Digital Library

[21]

David A. Huffman. 1957. The design and use of hazard-free switching networks. J. ACM 4, 1 (Jan. 1957), 47--62.

Digital Library

[22]

Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah. 2018. On the complexity of hazard-free circuits. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18). ACM, New York, NY, 878--889.

Digital Library

[23]

Stasys Jukna. 2012. Boolean Function Complexity—Advances and Frontiers. Algorithms and combinatorics, Vol. 27. Springer.

Digital Library

[24]

Stephen Cole Kleene. 1938. On notation for ordinal numbers. J. Symbol. Logic 3, 4 (1938), 150--155. http://www.jstor.org/stable/2267778

[25]

Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland.

[26]

Stephan Körner. 1966. Experience and Theory : An Essay in the Philosophy of Science. Routledge 8 Kegan Paul, London.

[27]

François Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC’14). ACM, New York, NY, 296--303.

Digital Library

[28]

Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--71.

[29]

Grzegorz Malinowski. 2014. Kleene logic and inference. Bull. Section Logic 43, 1/2 (2014), 42--52.

[30]

Leonard R. Marino. 1981. General theory of metastable operation. IEEE Trans. Comput. 30, 2 (1981), 107--115.

Digital Library

[31]

K. Mehlhorn and Z. Galil. 1976. Monotone switching circuits and boolean matrix product. Computing 16, 1 (01 Mar. 1976), 99--111.

[32]

M. Mukaidono. 1972. On the B-ternary logical function—A ternary logic considering ambiguity. Syst. Comput. Controls 3, 3 (1972), 27--36.

[33]

M. Mukaidono. 1983. Advanced results on application of fuzzy switching functions to hazard detection. In Advances in Fuzzy Sets, Possibility Theory and Applications, P. P. Wong (Ed.). Plenum Publishing, 335--349.

[34]

M. Mukaidono. 1983. Regular ternary logic functions—Ternary logic functions suitable for treating ambiguity. In Proceedings of the 13th International Symposium on Multiple-Valued Logic. IEEE Computer Society Press, 286--291.

[35]

S. M. Nowick and D. L. Dill. 1992. Exact two-level minimization of hazard-free logic with multiple-input changes. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 626--630.

Digital Library

[36]

Michael S. Paterson. 1975. Complexity of monotone networks for Boolean matrix product. Theoret. Comput. Sci. 1, 1 (1975), 13--20.

Digital Library

[37]

Pedro Ponce-Cruz and Fernando D. Ramírez-Figueroa. 1979. Intelligent Control Systems with LabVIEW. Springer-Verlag, London.

Digital Library

[38]

Vaughan R. Pratt. 1974. The power of negative thinking in multiplying boolean matrices. In Proceedings of the 6th Annual ACM Symposium on Theory of Computing (STOC’74). ACM, New York, NY, 80--83.

Digital Library

[39]

Ran Raz and Avi Wigderson. 1992. Monotone circuits for matching require linear depth. J. ACM 39, 3 (1992), 736--744.

Digital Library

[40]

Alexander A. Razborov. 1985. Lower bounds on monotone complexity of the logical permanent. Math. Notes 37, 6 (1985), 485--493.

[41]

Raul Rojas. 1996. Neural Networks—A Systematic Introduction. Springer-Verlag, Berlin.

Digital Library

[42]

Volker Strassen. 1969. Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354--356.

Digital Library

[43]

G. Tarawneh and A. Yakovlev. 2012. An RTL method for hiding clock domain crossing latency. In Proceedings of the 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS’12). 540--543.

[44]

G. Tarawneh, A. Yakovlev, and T. Mak. 2014. Eliminating synchronization latency using sequenced latching. IEEE Trans. Very Large Scale Integr. Syst. 22, 2 (Feb. 2014), 408--419.

Digital Library

[45]

É. Tardos. 1988. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica 8, 1 (Mar. 1988), 141--142.

[46]

Mohit Tiwari, Hassan M. G. Wassel, Bita Mazloom, Shashidhar Mysore, Frederic T. Chong, and Timothy Sherwood. 2009. Complete information flow tracking from the gates up. SIGARCH Comput. Archit. News 37, 1 (Mar. 2009), 109--120.

Digital Library

[47]

S. H. Unger. 1995. Hazards, critical races, and metastability. IEEE Trans. Comput. 44, 6 (June 1995), 754--768.

Digital Library

[48]

Ingo Wegener. 1982. Boolean functions whose monotone complexity is of size n<sup>2</sup>/log n. Lect. Notes Comput. Sci. 21 (Nov. 1982), 213--224.

[49]

A. C. Yao. 1989. Circuits and local computation. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC’89). ACM, New York, NY, 186--196.

Digital Library

[50]

Michael Yoeli and Shlomo Rinon. 1964. Application of ternary algebra to the study of static hazards. J. ACM 11, 1 (Jan 1964), 84--97.

Digital Library

[51]

Y. Zisapel, M. Krieger, and J. Kella. 1979. Detection of hazards in combinational switching circuits. IEEE Trans. Comput. C-28, 1 (Jan. 1979), 52--56.

Digital Library

Cited By

Deligkas AFearnley JHollender AMelissourgos T(2024)Pure-Circuit: Tight Inapproximability for PPADJournal of the ACM10.1145/367816671:5(1-48)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1145/3678166
Jukna S(2021)Notes on Hazard-Free CircuitsSIAM Journal on Discrete Mathematics10.1137/20M135524035:2(770-787)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1137/20M1355240

Index Terms

On the Complexity of Hazard-free Circuits
1. Theory of computation
  1. Computational complexity and cryptography
    1. Circuit complexity

Recommendations

On the complexity of hazard-free circuits
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded ...
Computational Complexity of Controllability/Observability Problems for Combinational Circuits

The computational complexity of fault detection problems and various controllability and observability problems for combinational logic circuits are analyzed. It is shown that the fault detection problem is still NP-complete for monotone circuits ...
Notes on Hazard-Free Circuits

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit, that is, a Boolean AND, OR, NOT ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 66, Issue 4

Networking, Computational Complexity, Design and Analysis of Algorithms, Real Computation, Algorithms, Online Algorithms and Computer-aided Verification

August 2019

299 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3338848

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2019 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2019

Accepted: 01 March 2019

Revised: 01 January 2019

Received: 01 July 2018

Published in JACM Volume 66, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
906
Total Downloads

Downloads (Last 12 months)184
Downloads (Last 6 weeks)31

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deligkas AFearnley JHollender AMelissourgos T(2024)Pure-Circuit: Tight Inapproximability for PPADJournal of the ACM10.1145/367816671:5(1-48)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1145/3678166
Jukna S(2021)Notes on Hazard-Free CircuitsSIAM Journal on Discrete Mathematics10.1137/20M135524035:2(770-787)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1137/20M1355240

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents