Аннотация:Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple, i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice as is because Kolmogorov complexity is not computable.
In recent years resource-bounded algorithmic statistics were created. In this paper we prove a polynomial-time version of the following result of ‘classic’ algorithmic statistics.
Assume that some data were obtained as a result of some unknown experiment. What kind of data should we expect in similar situation (repeating the same experiment)? It turns out that the answer to this question can be formulated in terms of algorithmic statistics. We prove a polynomial-time version of this result under a reasonable complexity theoretic assumption. The same assumption was used by Antunes and Fortnow.