Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874107 | Information Processing Letters | 2018 | 12 Pages |
Abstract
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 FPNP 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oliver Keszocze, Mathias Soeken, Rolf Drechsler,