Standard

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 journalArticlepeer-review

Harvard

Ryabko, B 2015, 'Complexity of approximating functions on real-life computers', International Journal of Foundations of Computer Science, vol. 26, no. 1, pp. 153-157. https://doi.org/10.1142/S0129054115500082

APA

Ryabko, B. (2015). Complexity of approximating functions on real-life computers. International Journal of Foundations of Computer Science, 26(1), 153-157. https://doi.org/10.1142/S0129054115500082

Vancouver

Ryabko B. Complexity of approximating functions on real-life computers. International Journal of Foundations of Computer Science. 2015 Jan 25;26(1):153-157. doi: 10.1142/S0129054115500082

Author

Ryabko, Boris. / Complexity of approximating functions on real-life computers. In: International Journal of Foundations of Computer Science. 2015 ; Vol. 26, No. 1. pp. 153-157.

BibTeX

@article{fc7545762708414881e8036a27bb3a88,
title = "Complexity of approximating functions on real-life computers",
abstract = "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, ε).",
keywords = "Computational complexity, information theory, performance evaluation, ε-entropy",
author = "Boris Ryabko",
year = "2015",
month = jan,
day = "25",
doi = "10.1142/S0129054115500082",
language = "English",
volume = "26",
pages = "153--157",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "1",

}

RIS

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