Complexity of approximating functions on real-life computers. / Ryabko, Boris.
In: International Journal of Foundations of Computer Science, Vol. 26, No. 1, 25.01.2015, p. 153-157.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 25331442