[section] [section]

[section] [section] [section]

Optimal predictors turn out to be unique up to a certain equivalence relation. The existence of optimal predictors depends on the specific variety you consider. We show that in the non-uniform case (allowing advice) there is a variety of optimal predictors that exist for completely arbitrary problems. Uniform optimal predictors of this kind exist for a certain class of problems we call “generatable” which is can be very roughly regarded as an average-case analogue of \(\textsc{NP} \cap \textsc{coNP}\). More generally mapping the class of problems which admit optimal predictors allows for much further research.