TY - JOUR

T1 - Complexity of approximating functions on real-life computers

AU - Ryabko, Boris

PY - 2015/1/25

Y1 - 2015/1/25

N2 - We address the problem of estimating the computation time necessary to approximate a function on a real computer. Our approach gives a possibility to estimate the minimal time needed to compute a function up to the specified level of error. This can be explained by the following example. Consider the space of functions defined on [0,1] whose absolute value and the first derivative are bounded by C. In a certain sense, for almost every such function, approximating it on its domain using an Intel x86 computer, with an error not greater than ε, takes at least k(C, ε) seconds. Here we show how to find k(C, ε).

AB - We address the problem of estimating the computation time necessary to approximate a function on a real computer. Our approach gives a possibility to estimate the minimal time needed to compute a function up to the specified level of error. This can be explained by the following example. Consider the space of functions defined on [0,1] whose absolute value and the first derivative are bounded by C. In a certain sense, for almost every such function, approximating it on its domain using an Intel x86 computer, with an error not greater than ε, takes at least k(C, ε) seconds. Here we show how to find k(C, ε).

KW - Computational complexity

KW - information theory

KW - performance evaluation

KW - ε-entropy

UR - http://www.scopus.com/inward/record.url?scp=84928389522&partnerID=8YFLogxK

U2 - 10.1142/S0129054115500082

DO - 10.1142/S0129054115500082

M3 - Article

AN - SCOPUS:84928389522

VL - 26

SP - 153

EP - 157

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 1

ER -