The complexity of error metrics

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.