Computational complexity of prediction strategies
| dc.contributor.author | Podnieks, Karlis | |
| dc.date.accessioned | 2015-11-28T17:49:32Z | |
| dc.date.available | 2015-11-28T17:49:32Z | |
| dc.date.issued | 1977 | |
| dc.description.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). | en_US |
| dc.identifier.citation | K. Podnieks. Computational complexity of prediction strategies. In: Theory of Algorithms and Programs, Vol. 3, Latvia State University, 1977, pp. 89–102 | en_US |
| dc.identifier.uri | https://dspace.lu.lv/dspace/handle/7/31218 | |
| dc.language.iso | rus | en_US |
| dc.publisher | Latvia State University | en_US |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | machine learning | en_US |
| dc.subject | inductive inference | en_US |
| dc.subject | Research Subject Categories::MATHEMATICS | en_US |
| dc.subject | function prediction | en_US |
| dc.title | Computational complexity of prediction strategies | en_US |
| dc.type | info:eu-repo/semantics/article | en_US |