The complexity of error metrics

Oliver Keszöcze, Mathias Soeken, Rolf Drechsler

In: Information Processing Letters 139 Seiten 1-7 Elsevier 2018.


Approximate computing exploits the fact that many applications do not require the results to be exact but not to exceed a threshold in a given error metric. Algorithms in approximate computing require to compute the error of the approximation in order to measure its quality. In this paper, the computational complexity of several of such error metrics commonly used in approximate computing is investigated. We show that these metrics lie within the complexity classes and #P and, therefore, are hard to compute. We further classify the error metrics into two classes. The framework used in this generalization is then used to exemplary develop specialized error metrics.

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