Computational complexity of prediction strategies
Date
1977
Authors
Podnieks, Karlis
Journal Title
Journal ISSN
Volume Title
Publisher
Latvia State University
Abstract
The value f(m+1) is predicted from given f(1), ..., f(m). For every enumeration T(n, x) there is a strategy that predicts the n-th function of T making no more than log2(n) errors (Barzdins-Freivalds). It is proved in the paper that such "optimal" strategies require 2^2^cm time to compute the m-th prediction (^ stands for expoentiation).
Description
Keywords
machine learning , inductive inference , Research Subject Categories::MATHEMATICS , function prediction
Citation
K. Podnieks. Computational complexity of prediction strategies. In: Theory of Algorithms and Programs, Vol. 3, Latvia State University, 1977, pp. 89–102