On the Computational Complexity of Error Metrics in Approximate Computing

Oliver Keszöcze, Mathias Soeken, Rolf Drechsler

In: Bernd Steinbach. Further Improvements in the Boolean Domain. Cambridge Scholars Publishing 2018.


The amount of digital systems supporting our daily life is increasing continuously. Improved technical facilities for their production have led to growing challenges for engineers and scientists working in the Boolean domain. A Boolean variable can only carry two different Boolean values: FALSE or TRUE (0 or 1), and has the best interference resistance in technical systems. However, a Boolean function exponentially depends on the number of its variables. This exponential complexity is the reason for major problems in the process of design and realization of circuits. According to Moore’s Law, the complexity of digital systems approximately doubles every 18 months. This requires comprehensive knowledge and techniques to solve very complex Boolean problems. This volume represents the third book in a series that provides further insights into the Boolean domain.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence