  With the developments in machine learning, there has been a surge in interest
and results focused on algorithms utilizing predictions, not least in online
algorithms where most new results incorporate the prediction aspect for
concrete online problems. While the structural computational hardness of
problems with regards to time and space is quite well developed, not much is
known about online problems where time and space resources are typically not in
focus. Some information-theoretical insights were gained when researchers
considered online algorithms with oracle advice, but predictions of uncertain
quality is a very different matter. We initiate the development of a complexity
theory for online problems with predictions, focusing on binary predictions for
minimization problems. Based on the most generic hard online problem type,
string guessing, we define a hierarchy of complexity classes and develop
notions of reductions, class membership, hardness, and completeness. Our
framework contains all the tools one expects to find when working with
complexity, and we illustrate our tools by analyzing problems with different
characteristics. Our work also implies the same results for classic online
problems without predictions.
