Solomonoff's theory of universal inductive inference (Inf. Control., 1964) provides a framework for predicting a future observation from past ones generated by an arbitrary randomized Turing machine. The theory is founded on the notion of resource-unbounded Kolmogorov complexity, and thus Solomonoff's approach cannot be realized as a finite-step algorithm.

In this paper, we develop a complexity-theoretic counterpart of Solomonoff's theory. We construct a polynomial-time universal inductive inference algorithm that extrapolates a sequence of symbols generated by any unknown $t$-time randomized Turing machine in time polynomial in $t$, assuming that time-bounded Kolmogorov complexity can be computed in average polynomial time. Previously, it was not even known whether distributional learning for all polynomial-size circuits—an i.i.d. analogue of inductive inference—is feasible if NP is easy on average. Moreover, without any unproven assumption, we characterize a distribution of sequences for which there exists an efficient inductive inference algorithm by the notion of prequential compression. We also construct an optimal efficient inductive inference algorithm that performs as well as any other efficient algorithms.

Our universal inductive inference algorithm relies on (1) a new algorithmic proof of a chain rule for time-bounded algorithmic information, and (2) an online algorithm that boosts the "confidence" of our inductive inference algorithm.

This version significantly improves upon the previous one, which did not even include the current main theorems (Theorems 2.1 and 2.3). In particular, it introduces new technical contributions, confidence boosting and characterization via prequential compression, and substantially revises both the title and nearly the entire content, while incorporating the main result of the previous version as Theorem 2.2.

Inductive inference, introduced by Solomonoff (Information and Control, 1964), is a foundational concept in knowledge acquisition, formulated as the task of extrapolating a sequence of symbols. In his seminal work, Solomonoff established a fundamental theorem for recursion-theoretic universal inductive inference, applicable to sequences generated by all Turing machines, based on the (uncomputable) task of computing Kolmogorov complexity.

In this work, we present a complexity-theoretic counterpart to Solomonoff’s theorem: we construct an efficient universal inductive inference algorithm, applicable to sequences efficiently generated by all randomized Turing machines, assuming that time-bounded Kolmogorov complexity can be efficiently approximated. This assumption is known to follow from the average-csae easiness of NP. As corollaries, we obtain various worst-case learning algorithms, such as distributional learning and learning adaptively changing distributions, under the assumption that NP is easy on average.

Our inductive inference algorithm and its analysis build on techniques developed in meta-complexity theory. At a high level, the algorithm divides a given sequence of symbols into two parts, "advice" and "context", and extrapolates the next symbol of the context according to the time-bounded universal distribution given the advice. We prove that this algorithm avoids computationally deep strings, which are hard instances for every average-case algorithm.