Complexity Classes for Online Problems with and without Predictions

Abstract 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, considering minimization problems and one prediction bit per request. Based on the most generic hard online problem type, string guessing, we define a family of hierarchies of complexity classes (indexed by pairs of error measures) 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. In addition, we show that known lower bounds for paging with discard predictions apply directly to all hard problems for each class in the hierarchy based on the canonical pair of error measures. This paging problem is not complete for these classes. Our work also implies corresponding complexity classes for classic online problems without predictions, with the corresponding complete problems. 1 Introduction In computational complexity theory, one aims at classifying computational problems based on their hardness, by relating them via hardness-preserving mappings, referred to as reductions. Most commonly seen are time and space complexity, where problems are classified based on how much time or space is needed to solve the problem. Our primary aim is to classify online minimization problems with predictions based on the competitiveness of best possible deterministic online algorithms for each problem. In initiating this line of research, we consider minimization problems with binary predictions, encoding an optimal solution and given one bit at a time together with the requests. Our framework has recently been extended to maximization problems [8]. An online problem is an optimization problem where the input is revealed to an online algorithm in a piece-wise fashion in the form of requests. When a request arrives, an online algorithm must make an irrevocable decision about the request before the next request arrives. When comparing the quality of online algorithms, we use the standard competitive analysis framework [42] (see [12, 36]), where the competitiveness of an online algorithm is computed by comparing the algorithm’s performance to an offline optimal algorithm’s performance. Competitive analysis is a framework for worst-case guarantees, where we say that an algorithm is c-competitive if, asymptotically over all possible input sequences, its cost is at most a factor c times the cost of the optimal offline algorithm. With the increased availability and improved quality of predictions from machine learning software, efforts to utilize predictions in online algorithms have increased dramatically [3]. Typically, one studies the competitiveness of online algorithms that have access to additional information about the instance through (unreliable) predictions. Ideally, such algorithms should perform perfectly when the predictions are error-free (the competitiveness in this case is called the consistency), and perform as well as the best purely online algorithm when the predictions are erroneous (robustness). There is also a desire that an algorithm’s competitiveness degrades gracefully from the consistency to the robustness as the predictions get worse (often referred to as smoothness). In particular, the performance should not plummet due to minor errors. To establish smoothness, it is necessary to have some measure of how wrong a prediction is. Thus, results of this type are based on some error measure. The complexity of algorithms with predictions has also been considered in a different context, dynamic graph problems [31]. However, Henzinger et al. study the time complexity of dynamic data structures, whereas we create complexity classes where the hardness is based on competitiveness. The basis for our complexity classes is a parameterized version of asymmetric string guessing [17], a generic hard online problem, where each request is simply a prompt for the algorithm to guess a bit. String guessing (not necessarily asymmetric) [9] has played a fundamental role in what is often referred to as advice complexity [10, 16, 26, 29, 32], where online algorithms have access to oracle-produced information about the instance which, in our context, can be considered infallible predictions. The same standard string guessing problem has also been used for the advice complexity of priority algorithms [11, 13, 21]. Specifically, we use Online (1, t)-Asymmetric String Guessing with Unknown History and Predictions (\(\textsc{ASG}_{t}\)), which will be our base family of complete problems, establishing a strict hierarchy based on the parameter, t. The cost of processing an input is the number of guesses of 1 plus t times the number of incorrect guesses of 0. Other variants of Asymmetric String Guessing have been used before in [39], considering connections between advice complexity and randomization, as well as in [18] where weighted versions of problems proven hard with respect to advice complexity in [17] are considered. We define complexity classes, \(\mathcal {C}_{\eta _0,\eta _1}^{t}\), parameterized by \(t\in \mathbb {Z}^+ \cup \{\infty \}\) and a pair of error measures, \((\eta _0,\eta _1)\), with certain properties. To prove that a problem, P, is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, one must show that P is as hard as \(\textsc{ASG}_{t}\), and to prove membership in \(\mathcal {C}_{\eta _0,\eta _1}^{t}\), one must show that \(\textsc{ASG}_{t}\) is as hard as P. If both are true, P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete. The as-hard-as relation is transitive, so our framework provides all the usual tools: if a subproblem of some problem is hard, the problem itself is hard, one can reduce from the most convenient complete problem, etc. Thus, working with our complexity classes is similar to working with, e.g., NP, MAX-SNP [40], the W-hierarchy [27], and APX [6], in that hardness results are obtained by proving the existence of special types of reductions that preserve properties related to hardness. However, we obtain performance bounds that are independent of any conjectures. Deriving lower bounds on the competitiveness of algorithms based on the hardness of string guessing has been considered before [9, 11, 29], with different objectives. The closest related work is in [17], where one of the base problems we use in this paper, \((1,\infty )\)-Asymmetric String Guessing with Unknown History, was used as the base problem for the complexity class AOC; AOC-complete problems are hard online problems with advice. Note that despite the similarities, working with advice and predictions are quite different matters. In advice complexity, the competitive ratio is a function of the number of advice bits available. Working with predictions, competitiveness is a function of the quality, not the quantity, of information about the input. Thus, results cannot be translated between AOC and the complexity classes of this paper. Moreover, AOC is only one complexity class, not a hierarchy. Strong lower bounds in the form of hardness results from our framework can be seen as indicating the insufficiency of a binary prediction scheme for a problem. Proving that a problem is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard suggests that one cannot solve it better than blindly trusting the predictions, when using binary predictions, giving a rather poor result. Hence, proving that a problem is hard serves as an argument for needing a richer prediction scheme for the problem, or possibly a more accurate way of measuring prediction error. Our main contribution is an initial framework enabling a complexity theory for online algorithms with binary predictions. In this framework, proving that a problem is hard for a class currently requires that the predictions be binary encodings of the output the online algorithm should produce. Using this framework, we prove hardness and class membership results for several problems, including showing the completeness of Online t-Bounded Degree Vertex Cover (\(\textsc{VC}_{t}\)) for \(\mathcal {C}_{\eta _0,\eta _1}^{t}\). Thus, \(\textsc{VC}_{t}\), or any other complete problem, could be used as the basis for the complexity classes instead of \(\textsc{ASG}_{t}\). However, we follow the tradition from advice complexity and use a string guessing problem, \(\textsc{ASG}_{t}\), as its lack of structure offers simpler proofs. We illustrate the relative hardness of the problems we investigate in Fig. 1. Worth noting is that by choosing the appropriate pair of error measures, our set-up immediately gives the same hardness results for purely online problems, that is, for algorithms without predictions. As a soundness test for our framework, we consider the paging problem. Intuitively, researchers in online algorithms would expect that problem to be easier than, for instance, \(\textsc{ASG}_{t}\) or \(\textsc{VC}_{t}\), because it seems that much more information is available. And, indeed, we can prove that, as opposed to those two problems, paging with discard predictions is not a complete problem for the complexity class \(\mathcal {C}_{\mu _0,\mu _1}^{t}\) from our framework. Furthermore, maybe surprisingly, this non-complete paging problem gives rise to new lower bounds for \(\mathcal {C}_{\mu _0,\mu _1}^{t}\)-complete problems. 2 Preliminaries In this paper, we consider online problems with binary predictions. From now on, we will not keep emphasizing that they are binary but simply refer to them as predictions. The algorithms have to make an irrevocable decision, \(y_i\), for each request. With the exception of the paging problem, we focus on problems, where these decisions (the \(y_i\)’s) are also binary. For any problem, P, as just described, we let \(\mathcal {{I}}_{P}\) be the collection of instances of P, we let \(\mathcal {A}_{P}\) be the set of algorithms for P, and we let \(\textsc{Opt}_P\) be a fixed optimal algorithm for P. In our notation, an instance of P is a triple \(I = (x,\hat{x},r)\), consisting of two bitstrings \(x,\hat{x} \in \{0,1\}^n\), and a sequence of requests \(r = \langle r_1,r_2,\ldots ,r_n\rangle \) for P. The bitstring x is an encoding of \(\textsc{Opt}_P\)’s solution, and \(\hat{x}\) is a prediction of x. When an algorithm, \(\textsc{Alg}\), receives the request \(r_i\), it also receives the prediction \(\hat{x}_i\) to aid its decision (represented by a bit, \(y_i\)) for \(r_i\). What information is contained in each request, \(r_i\), and the meaning of the bits \(x_i\), \(\hat{x}_i\), and \(y_i\), will be specified for each problem. When there can be no confusion, we write \(\textsc{Opt}\) instead of \(\textsc{Opt}_P\). Given an algorithm, \(\textsc{Alg}\in \mathcal {A}_{P}\), and an instance, \(I \in \mathcal {{I}}_{P}\), we let \(\textsc{Alg}[I]\) be \(\textsc{Alg}\)’s solution to I, and \(\textsc{Alg}(I)\) be the cost of \(\textsc{Alg}[I]\). 2.1 Competitiveness and Error Measures For purely online algorithms, we use the following definition of competitiveness: An algorithm, \(\textsc{Alg}\), for a minimization problem, is c-competitive if there exists a constant, \(\kappa \), called the additive term, such that for all instances \(I = (x,r) \in \mathcal {{I}}_{P}\), We extend the definition of competitiveness to online algorithms with predictions, based on [4]. Here, the competitiveness of an algorithm is written as a function of two error measuresFootnote 1, \(\eta _0\) and \(\eta _1\), where \(\eta _b\) is a function of the bits incorrectly predicted to be b. Definition 1 Let \((\eta _0,\eta _1)\) be a pair of error measures, let P be an online minimization problem with predictions, and let \(\textsc{Alg}\) be a deterministic online algorithm for P. If there exist three maps \(\alpha , \beta , \gamma :\mathcal {{I}}_{P} \rightarrow \mathbb {R}_{\geqslant 0}\) and an additive constant, \(\kappa \), such that for all \(I \in \mathcal {{I}}_{P}\), then \(\textsc{Alg}\) is \((\alpha ,\beta ,\gamma )\)-competitive with respect to \((\eta _0,\eta _1)\) . When \((\eta _0,\eta _1)\) is clear from the context, we simply write that \(\textsc{Alg}\) is \((\alpha ,\beta ,\gamma )\)-competitive. If \(\kappa \leqslant 0\), for all \(I \in \mathcal {{I}}_{P}\), then \(\textsc{Alg}\) is strictly \((\alpha ,\beta ,\gamma )\)-competitive. If \(\textsc{Alg}\) is not \((\alpha ,\beta ,\gamma )\)-competitive for any \(\alpha ,\beta ,\gamma \), we simply say that it is not competitive. In our notation, \(\alpha \), \(\beta \), and \(\gamma \)’s dependency on I is kept implicit, as is tradition. For the results in this paper, it is not necessary that \(\alpha \), \(\beta \), and \(\gamma \) are functions of the input. However, we are developing a framework that should be generally applicable, and many results from standard competitive analysis have competitive ratios that are functions of the input (size). Examples include graph coloring, dynamic binary search trees, and some scheduling problems. Further, observe that any purely online \(\alpha \)-competitive algorithm is \((\alpha ,0,0)\)-competitive with respect to any pair of error measures \((\eta _0,\eta _1)\). Since the performance of an algorithm is not measured by a competitive ratio, but by a triple, \((\alpha ,\beta ,\gamma )\), we cannot establish a total ordering of algorithms. Instead, we consider the concept of Pareto-optimality. Definition 2 An \((\alpha ,\beta ,\gamma )\)-competitive algorithm is called Pareto-optimal for a problem, P, if, for any \(\varepsilon > 0\), there cannot exist an \((\alpha - \varepsilon ,\beta ,\gamma )\)-, an \((\alpha ,\beta -\varepsilon ,\gamma )\)-, or an \((\alpha ,\beta ,\gamma - \varepsilon )\)-competitive algorithm for P. 2.1.1 Error Measures of Interest We define a pair of error measures, \((\mu _0,\mu _1)\), equivalent to the pair of error measures from [4], where \(\mu _b\) is the number of incorrect predictions of \(b \in \{0,1\}\): Definition 3 For any instance, \(I = (x,\hat{x},r)\), The following pair of error measures allows us to extend the results of this paper to purely online algorithms. Definition 4 For any instance, \(I = (x,\hat{x},r)\), \(Z_0(I) = Z_1(I) = 0\). In this paper, we will consider error measures with the property that insertion of a finite number of correctly predicted bits into an instance does not increase the error: Definition 5 An error measure \(\eta \) is called insertion monotone if for any instance I, \(\eta (I') \leqslant \eta (I)\), where \(I'\) is obtained by inserting a finite number of correctly predicted requests into I. Clearly \(\mu _b\) and \(Z_b\), \(b \in \{0,1\}\), are insertion monotone.Footnote 2 Although formally, the predictions \(\hat{x}\) exist in general results that assume insertion monotone measures, these predictions are not used in the analysis when \(Z_b\) is used; the competitiveness must be obtained independently of the correctness of the prediction. Thus, these results hold for purely online algorithms, where the predictions do not exist. 2.2 Graph Problems All graph problems mentioned in this paper are studied in the vertex-arrival model, the most standard for online graph problems. Hence, for any graph \(G = (V,E)\), each request \(r_i\) is a vertex \(v_i \in V\) that is revealed together with all edges of the form \((v_j,v_i) \in E\), where \(j \leqslant i\). We only consider simple unweighted graphs. 3 Asymmetric String Guessing: A Collection of Hard Problems Given a bitstring, x, and a \(t \in \mathbb {Z}^+ \cup \{\infty \}\), the task of an algorithm for (1, t)-Asymmetric String Guessing (\(\textsc{ASG}_{t}\)) is to correctly guess the contents of x. The cost of a solution is the number of guesses of 1 plus t times the number of incorrect guesses of 0. When \(t=\infty \), the problem corresponds to the string guessing problem considered in [17]. We now define the problem more formally. Definition 6 For any \(t \in \mathbb {Z}^+ \cup \{\infty \}\), an instance of the problem Online (1, t)-Asymmetric String Guessing with Unknown History and Predictions (\(\textsc{ASG}_{t}\)) is a triple \(I = (x,\hat{x},r)\), where \(x = \langle x_1, \ldots x_n \rangle \) and \(\hat{x} = \langle \hat{x}_1, \ldots , \hat{x}_n \rangle \) are bitstrings and \(r=\langle r_1, \ldots , r_n \rangle \) is a sequence of requests. Each request, \(r_i\), is a prompt for the algorithm to output a bit, \(y_i\). Together with \(r_i\), \(\hat{x}_i\) is revealed, but x is only revealed after the last request. Given an instance \(I \in \mathcal {{I}}_{\textsc{ASG}_{t}}\) of \(\textsc{ASG}_{t}\) with \(t \in \mathbb {Z}^+\), where \(y_i\) is \(\textsc{Alg}\)’s i’th guess. When \(t = \infty \), we abbreviate \(\textsc{ASG}_{t}\) by \({\textsc{ASG}}\) and rewrite the objective function as: 3.1 \(\varvec{\textsc{ASG}_{t}}\) without Predictions For all \(t \in \mathbb {Z}^+ \cup \{\infty \}\), we may consider \(\textsc{ASG}_{t}\) as a purely online problem by omitting \(\hat{x}\). We briefly state the main results on \(\textsc{ASG}_{t}\) without predictions. The following observation is well-known. Observation 1 ([17]) For any purely online algorithm, \(\textsc{Alg}\), for \({\textsc{ASG}}\), there is no function, f, such that \(\textsc{Alg}\) is f(n)-competitive. The observation follows from the fact that if an algorithm, \(\textsc{Alg}\), ever guesses 0, there is an instance where \(\textsc{Alg}\) guesses 0 on a true 1, and thus incurs cost \(\infty \). On the other hand, if \(\textsc{Alg}\) only guesses 1, there is an instance consisting of only 0’s, such that \(\textsc{Opt}\) will incur cost 0 while the cost of \(\textsc{Alg}\) is equal to the length of the sequence. Theorem 2 Let \(t \in \mathbb {Z}^+\) and \(\varepsilon > 0\). Then, for \(\textsc{ASG}_{t}\), the following hold. - (i) The algorithm that always guesses 0 is t-competitive. - (ii) There is no purely online \((t-\varepsilon )\)-competitive deterministic algorithm. Proof We consider each item separately. - Towards: - (i): Let \(\textsc{Alg}\) be the algorithm that always guesses 0. Then, for any instance \(I = (x,r) \in \mathcal {{I}}_{\textsc{ASG}_{t}}\), $$\begin{aligned} \textsc{Alg}(I) = \sum _{i=1}^{n} t \cdot x_i = t \cdot \sum _{i=1}^{n} x_i = t \cdot \textsc{Opt}(I). \end{aligned}$$ - Towards: - (ii): Assume towards contradiction that there exists a deterministic purely online \((t-\varepsilon )\)-competitive algorithm, \(\textsc{Alg}\), for some \(\varepsilon >0\). Then, there exists a constant \(0<\varepsilon '<1\) such that \(\textsc{Alg}\) is \((t-\varepsilon ')\)-competitive. This means that there exists an additive term, \(\kappa \in O(1)\), such that, for all \(I = (x,r) \in \mathcal {{I}}_{\textsc{ASG}_{t}}\), $$\begin{aligned} \textsc{Alg}(I) \leqslant (t-\varepsilon ') \cdot \textsc{Opt}(I) + \kappa . \end{aligned}$$(1) We define a family \(\{I^n\}_{n\in \mathbb {Z}^+}\) of instances, where, for any \(n \in \mathbb {Z}^+\) and any \(i \in \{1,2,\ldots ,n\}\), the i’th true bit in \(I^n = (x^n,r^n)\) is where \(y_i^n\) is \(\textsc{Alg}\)’s i’th guess when run on \(I^n\). Since \(\textsc{Alg}\) is deterministic, the collection \(\{I^n\}_{n\in \mathbb {Z}^+}\) is well-defined. For each \(i = 1,2,\ldots ,n\), if \(y^n_i = 0\), then \(x_i^n = 1\), and so \(\textsc{Alg}\) incurs cost t, and \(\textsc{Opt}\) incurs cost 1. On the other hand, if \(y_i^n = 1\), then \(x_i^n = 0\), and so \(\textsc{Alg}\) incurs cost 1, and \(\textsc{Opt}\) incurs cost 0. Hence, for each \(n \in \mathbb {Z}^+\), Combining (2) with Inequality (1), we get Solving for \(\kappa \), we get This contradicts that \(\kappa \in O(1)\). \(\square \) 3.2 \(\varvec{\textsc{ASG}_{t}}\) with Predictions and Error Measures \(\varvec{(\mu _0,\mu _1)}\) Now, we turn to the hardness of \(\textsc{ASG}_{t}\) with predictions, focusing on the pair \((\mu _0,\mu _1)\) of error measures. An obvious algorithm for \(\textsc{ASG}_{t}\) is Follow-the-Predictions (\(textsc{FtP}\)), which always sets its guess, \(y_i\), to the given prediction, \(\hat{x}_i\). Theorem 3 For any \(t \in \mathbb {Z}^+\) and any \(\alpha \) and \(\beta \) such that \(\alpha \geqslant 1\) and \(\alpha + \beta \geqslant t\), \(textsc{FtP}\) is strictly \((\alpha ,\beta ,1)\)-competitive for \(\textsc{ASG}_{t}\) with respect to \((\mu _0,\mu _1)\). Proof Consider any \(I = (x,\hat{x},r) \in \mathcal {{I}}_{\textsc{ASG}_{t}}\) with \(n = \left\lvert r \right\rvert \), and let \(y_i\) be \(textsc{FtP}\)’s output on \(r_i\), \(1 \leqslant i \leqslant n\). Then, \(\square \) Corollary 4 For any \(t \in \mathbb {Z}^+\), \(textsc{FtP}\) is strictly \((1,t-1,1)\)-competitive for \(\textsc{ASG}_{t}\) with respect to \((\mu _0,\mu _1)\). In the following, we extend a lower bound on Paging with Discard Predictions by Antoniadis et al. [4] to \(\textsc{ASG}_{t}\). For completeness, we state the theorem here, though restricted to \(\textsc{ASG}_{t}\) and without proof. In Theorem 43 in Section 7.1.1, it is restated and proven in a more general form. Theorem 5 Let \(t \in \mathbb {Z}^+\). Then, for any \((\alpha ,\beta ,\gamma )\)-competitive algorithm for \(\textsc{ASG}_{t}\) with respect to \((\mu _0,\mu _1)\), - (i) \(\alpha + \beta \geqslant t\) and - (ii) \(\alpha + (t-1) \cdot \gamma \geqslant t\). Next, we prove a negative result on the competitiveness of algorithms for \(\textsc{ASG}_{t}\) that does not follow from Theorem 5. Together with Theorems 2, 3, and 5, this negative result gives a complete classification of all Pareto-optimal algorithms for \(\textsc{ASG}_{t}\) with respect to \((\mu _0,\mu _1)\). Lemma 6 Let \(\textsc{Alg}\) be an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for \(\textsc{ASG}_{t}\) with respect to \((\mu _0,\mu _1)\). If \(\alpha < t\), then \(\gamma \geqslant 1\). Proof Assume towards contradiction that \(\textsc{Alg}\) is \((\alpha ,\beta ,\gamma )\)-competitive, where \(\alpha 0\) such that \(\alpha \leqslant t-\varepsilon \) and \(\gamma \leqslant 1-\varepsilon \). Consider the family \(\{I^n\}_{n\in \mathbb {Z}^+}\) of instances with \(I^n=(x^n,\hat{x}^n,r^n)\), where - \(\hat{x}^n = \langle 1^n \rangle \) and - \(x^n_i = 1 - y^n_i\), where \(y^n_i\) is \(\textsc{Alg}\)’s output on \(r^n_i\), \(1 \leqslant i \leqslant n\). Observe that \(x^n\) is well-defined since \(\textsc{Alg}\) is deterministic. Then, Since \(\textsc{Alg}\) is \((t-\varepsilon ,\beta ,1-\varepsilon )\)-competitive, there exists a \(\kappa \in O(1)\), such that, for each n, Combining (4) and (5) and solving for \(\kappa \), we get contradicting that \(\kappa \in O(1)\), since \(\varepsilon >0\). \(\square \) Theorem 7 Let \(\textsc{Alg}\) be an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for \(\textsc{ASG}_{t}\). Then, \(\textsc{Alg}\) is Pareto-optimal with respect to \((\mu _0,\mu _1)\), if and only if - (i) \(\alpha = t\) and \(\beta = \gamma = 0\), or - (ii) \(\alpha < t\), \(\beta = t - \alpha \), and \(\gamma = 1\). Proof We consider an \((\alpha ,\beta ,\gamma )\)-competitive algorithm and split the proof into two cases based on the value of \(\alpha \). - Case: - \(\alpha \geqslant t\): By Theorem 2(i), there exists a (t, 0, 0)-competitive algorithm. This algorithm is Pareto-optimal, since neither the second nor the third entry can be improved and by Theorem 2(ii), no \((t-\varepsilon ,0,0)\)-competitive algorithm exists. Thus, since \(\alpha \geqslant t\), \(\textsc{Alg}\) is Pareto-optimal, if and only if \(\alpha =t\) and \(\beta =\gamma =0\). - Case: - \(\alpha < t\): We note that \(\alpha \geqslant 1\), since no algorithm can be better than 1-consistent. Thus, by Theorem 3, the algorithm \(textsc{FtP}\) is \((\alpha , t-\alpha , 1)\)-competitive. Hence, for \(\textsc{Alg}\) to be Pareto-optimal, we must have that - (a): - \(\beta < t-\alpha \), - (b): - \(\gamma < 1\), or - (c): - \(\beta =t-\alpha \) and \(\gamma =1\). By Theorem 5(i), (a) is impossible, and, by Lemma 6, (b) is impossible. Thus, \(\textsc{Alg}\) is Pareto-optimal, if and only if \(\beta =t-\alpha \) and \(\gamma =1\). \(\square \) Note that by Theorem 2(i), the algorithm that always guesses zero is t-robust with respect to \((\mu _0,\mu _1)\). Corollary 8 \(textsc{FtP}\) and the algorithm that always guesses 0 are both Pareto-optimal with respect to \((\mu _0,\mu _1)\). Theorem 9 There is no competitive algorithm for \({\textsc{ASG}}\) with respect to \((\mu _0,\mu _1)\). Proof Suppose towards contradiction that for all sequences I, \(\textsc{Alg}(I) \leqslant \alpha \textsc{Opt}(I)+\beta \mu _0(I) +\gamma \mu _1(I)+\kappa \), where \(\alpha , \beta , \gamma :\mathcal {{I}}_{P} \rightarrow \mathbb {R}_{\geqslant 0}\) and \(\kappa \) is a constant. Consider the family \(\{I^n\}_{n\in \mathbb {Z}^+}\) of instances with \(I^n=(x^n,\hat{x}^n,r^n)\), where - \(\hat{x}^n = \langle 0^n \rangle \) and - \(x^n_i = 1 - y^n_i\), where \(y^n_i\) is \(\textsc{Alg}\)’s output on \(r^n_i\), \(1 \leqslant i \leqslant n\). Observe that \(x^n\) is well-defined since \(\textsc{Alg}\) is deterministic. Also, note that \(\mu _1(I^n)=0\), so \(\textsc{Alg}(I^n) \leqslant \alpha \textsc{Opt}(I^n)+\beta \mu _0(I^n) +\kappa \). If \(y^n_i=0\) for some i, then \(x^n_i=1\), so \(\textsc{Alg}\) incurs an infinite cost on \(r_i\). Thus, since neither \(\alpha \) nor \(\beta \) can be infinite, we have a contradiction. Otherwise, \(y^n_i=1\) for all i, so \(\textsc{Alg}(I^n)=n\), \(\textsc{Opt}(I^n)=0\) and \(\mu _0(I^n) = 0\), implying that \(n\leqslant \alpha \cdot 0+\beta \cdot 0+\kappa = \kappa \in O(1)\), giving a contradiction. Thus, \(\textsc{Alg}\) is not competitive. \(\square \) 4 Hierarchies of Complexity Classes In this section, we formally introduce the complexity classes, prove that, for each pair of error measures, they form a strict hierarchy, and show multiple fundamental structural properties of the complexity classes. 4.1 Relative Hardness and Reductions We define relative hardness as follows: Definition 7 Let P and Q be two online problems with predictions and error measures \((\eta _0,\eta _1)\) and \((\varphi _0,\varphi _1)\). We say that Q is as hard as P with respect to \((\varphi _0,\varphi _1)\) and \((\eta _0,\eta _1)\) , if the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for Q with respect to \((\varphi _0,\varphi _1)\) implies the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for P with respect to \((\eta _0,\eta _1)\). If the error measures are clear from the context, we simply say that Q is as hard as P. If Q is as hard as P, we use the notation \(Q\ge _{\text {o}} P\). We also say that P is no harder than Q, denoting this \(P \le _{\text {o}} Q\). It is not hard to see that the as-hard-as relation is both reflexive and transitive, but for completeness we give the proof here. Lemma 10 The relation as-hard-as is reflexive and transitive. Proof We prove each property separately. Towards Reflexivity Proving reflexivity translates to proving that the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm with respect to \((\eta _0,\eta _1)\) for P implies the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm with respect to \((\eta _0,\eta _1)\) for P, which is a tautology. Towards Transitivity Let P, W, and Q be online maximization problems with predictions with error measures \((\eta _0,\eta _1)\), \((\xi _0,\xi _1)\), and \((\varphi _0,\varphi _1)\), and assume that \(Q\ge _{\text {o}} W\) and that \(W \ge _{\text {o}} P\). Let \(\textsc{Alg}_Q \in \mathcal {A}_{Q}\) be an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for Q with respect to \((\varphi _0,\varphi _1)\). Since \(Q \ge _{\text {o}} W\) with respect to \((\varphi _0,\varphi _1)\) and \((\xi _0,\xi _1)\), the existence of \(\textsc{Alg}_Q\) implies the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm with respect to \((\xi _0,\xi _1)\) for W, say \(\textsc{Alg}_W\). Since \(W \ge _{\text {o}} P\) with respect to \((\xi _0,\xi _1)\) and \((\eta _0,\eta _1)\), the existence of \(\textsc{Alg}_W\) also implies the existence of an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for P with respect to \((\eta _0,\eta _1)\), and so \(Q \ge _{\text {o}} P\) with respect to \((\varphi _0,\varphi _1)\) and \((\eta _0,\eta _1)\). \(\square \) As a tool for proving hardness, we introduce the notion of reductions. A reduction from a problem, P, to another problem, Q, consists of a mapping of instances of P to instances of Q and a mapping from algorithms for Q to algorithms for P, with the requirement that \((\alpha , \beta , \gamma )\)-competitive algorithms for Q map to \((\alpha , \beta , \gamma )\)-competitive algorithms for P. In this paper, we use a restricted type of reduction: Definition 8 Let P and Q be online minimization problems with predictions, and let \((\eta _0,\eta _1)\) and \((\varphi _0,\varphi _1)\) be pairs of error measures for the predictions in P and Q, respectively. Let \(\rho = ({\rho }_{\textsc{a}},{\rho }_{\textsc{i}})\) be a tuple consisting of two maps, \({\rho }_{\textsc{a}}:\mathcal {A}_{Q}\rightarrow \mathcal {A}_{P}\) and \({\rho }_{\textsc{i}}:\mathcal {A}_{Q} \times \mathcal {{I}}_{P} \rightarrow \mathcal {{I}}_{Q}\). If there exists a constant, a, called the reduction term of \(\rho \), such that for each instance \(I_P \in \mathcal {{I}}_{P}\) and each algorithm \(\textsc{Alg}_Q \in \mathcal {A}_{Q}\), letting \(\textsc{Alg}_P = {\rho }_{\textsc{a}}(\textsc{Alg}_Q)\) and \(I_Q = {\rho }_{\textsc{i}}(\textsc{Alg}_Q,I_P)\), - (O1) \(\textsc{Alg}_P(I_P) \leqslant \textsc{Alg}_Q(I_Q) + a\), - (O2) \(\textsc{Opt}_Q(I_Q) \leqslant \textsc{Opt}_P(I_P)\), - (O3) \(\varphi _0(I_Q) \leqslant \eta _0(I_P)\), and \(\varphi _1(I_Q) \leqslant \eta _1(I_P)\), then \(\rho \) is called a strict online reduction from P to Q with respect to \((\eta _0,\eta _1)\) and \((\varphi _0,\varphi _1)\) . If the pairs \((\eta _0,\eta _1)\) and \((\varphi _0,\varphi _1)\) are clear from the context, then we simply say that \(\rho \) is a strict online reduction from P to Q, and write \(\rho :P \overset{r}{\rightarrow }\ Q\). In many of the examples to follow, we do not need a (nonzero) reduction term to establish the reductions, and we only mention the reduction term when needed. Lemma 11 Let \(\rho = ({\rho }_{\textsc{a}},{\rho }_{\textsc{i}})\) be a strict online reduction from a problem, P, with predictions and error measures \((\eta _0,\eta _1)\)to a problem, Q, with predictions and error measures \((\varphi _0,\varphi _1)\). Let \(\textsc{Alg}_Q \in \mathcal {A}_{Q}\) be an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for Q with respect to \((\varphi _0,\varphi _1)\), and let \(\textsc{Alg}_P = {\rho }_{\textsc{a}}(\textsc{Alg}_Q)\). Then, \(\textsc{Alg}_P\) is an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for P with respect to \((\eta _0,\eta _1)\). Proof Consider any instance, \(I_P \in \mathcal {{I}}_{P}\), and let \(I_Q = {\rho }_{\textsc{i}}(\textsc{Alg}_Q,I_P)\). Then, by Condition (O1) and Definition 1, there exists constants, a and \(\kappa \), such that \(\square \) Observation 12 Lemma 11 implies that strict online reductions serve the desired purpose of reductions: If there exists a strict online reduction \(\rho :P \overset{r}{\rightarrow }\ Q\), then \(Q \ge _{\text {o}} P\). When using strict online reductions, we will often simply use the term reduction. For the rest of this paper, we only consider reductions where the quality of predictions is measured using the same pair of error measures for both problems. 4.2 Introducing the Complexity Classes For any pair, \((\eta _0,\eta _1)\), of error measures and any \(t \in \mathbb {Z}^+ \cup \{\infty \}\), we define the complexity classes \(\mathcal {C}_{\eta _0,\eta _1}^{t}\) as the set of minimization problems with predictions that are no harder than \(\textsc{ASG}_{t}\) with respect to \((\eta _0,\eta _1)\): Definition 9 For each \(t \in \mathbb {Z}^+ \cup \{\infty \}\) and each pair of error measures, \((\eta _0,\eta _1)\), the complexity class \(\mathcal {C}_{\eta _0,\eta _1}^{t}\) is the closure of \(\textsc{ASG}_{t}\) under the as-hard-as relation with respect to \((\eta _0,\eta _1)\). Hence, for an online minimization problem, P, - \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\), if \(\textsc{ASG}_{t} \ge _{\text {o}} P\), - P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, if \(P \ge _{\text {o}} \textsc{ASG}_{t}\), and - P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete, if \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\) and P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard. The notation \(\mathcal {C}_{\eta _0,\eta _1}^{\infty }\) is usually abbreviated \(\mathcal {C}_{\eta _0,\eta _1}\). Observation 13 By Observation 12 and Lemma 11, if P and Q are \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete problems, then there exists an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for P if and only if there exists an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for Q. Thus, all of the results for \(\textsc{ASG}_{t}\) hold for the complete problems in \(\mathcal {C}_{\eta _0,\eta _1}^{t}\), and the upper bounds for \(\textsc{ASG}_{t}\) hold for all of the problems in \(\mathcal {C}_{\eta _0,\eta _1}^{t}\). Since the as-hard-as relation is reflexive, \(\textsc{ASG}_{t}\) is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete for any pair of error measures, \((\eta _0,\eta _1)\), and any t. Further, due to transitivity, we have the following simple but important properties that one would expect should hold for complexity classes. Theorem 14 Let \(t \in \mathbb {Z}^+ \cup \{\infty \}\) and let \((\eta _0,\eta _1)\) be any pair of error measures. - (i) If \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\) and \(P \ge _{\text {o}} Q\), then \(Q \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). - (ii) If P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard and \(Q \ge _{\text {o}} P\), then Q is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard. Proof We prove each item separately. - Towards (i): Since \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\), \(\textsc{ASG}_{t} \ge _{\text {o}} P\). Since \(P \ge _{\text {o}} Q\), transitivity implies that \(\textsc{ASG}_{t} \ge _{\text {o}} Q\), and thus \(Q \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). - Towards (ii): Since P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, \(P \ge _{\text {o}} \textsc{ASG}_{t}\). Since \(Q \ge _{\text {o}} P\), transitivity implies that \(Q \ge _{\text {o}} \textsc{ASG}_{t}\), and thus we conclude that Q is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard. \(\square \) This theorem implies results concerning special cases of a problem: Corollary 15 Let \(t \in \mathbb {Z}^+ \cup \{\infty \}\) and let \((\eta _0,\eta _1)\) be any pair of error measures. Let P and \(P_{{\text {sub}}}\) be online minimization problems such that \(\mathcal {{I}}_{P_{{\text {sub}}}} \subseteq \mathcal {{I}}_{P}\). - (i) If \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\), then \(P_{{\text {sub}}} \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). - (ii) If \(P_{{\text {sub}}}\) is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, then P is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard. Proof There exists a trivial online reduction, \(\rho :P_{{\text {sub}}} \overset{r}{\rightarrow }\ P\), obtained by setting \({\rho }_{\textsc{a}}(\textsc{Alg}) = \textsc{Alg}\) and \({\rho }_{\textsc{i}}(\textsc{Alg},I) = I\), for all algorithms \(\textsc{Alg}\in \mathcal {A}_{P}\) and all instances \(I \in \mathcal {{I}}_{P_{{\text {sub}}}}\). Hence, this is a consequence of Theorem 14. \(\square \) Note that Theorem 14 implies the following. Observation 16 Any \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete problem can be used instead of \(\textsc{ASG}_{t}\) as the base problem when defining \(\mathcal {C}_{\eta _0,\eta _1}^{t}\). As shown in Lemmas 25 and 28, the better known Online t-Bounded Degree Vertex Cover with Predictions is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-complete with respect to a wide range of pairs of error measures and may therefore be used as the basis of these complexity classes instead of \(\textsc{ASG}_{t}\). However, we chose to define the complexity classes as the closure of \(\textsc{ASG}_{t}\), due to it being a generic problem that is easily analyzed. Also, after establishing the first \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard problems, we may reduce from any \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard problem to prove hardness. Finally, a problem Q is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, if and only if \(Q \ge _{\text {o}} P\), for all \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). This is in line with the structure of other complexity classes such as NP and APX, where a problem Q is NP-hard, respectively APX-hard, if and only if there exists a polynomial-time reduction, respectively PTAS-reduction, from any problem in NP, respectively APX, to Q. Proposition 17 For every problem P in \(\mathcal {C}_{\mu _0,\mu _1}^{t}\), there exists a (t, 0, 0)-competitive algorithm and for every \(1 \leqslant \alpha \leqslant t\), there exists a \((\alpha ,t-\alpha ,1)\)-competitive algorithm for P. If P is \(\mathcal {C}_{\mu _0,\mu _1}^{t}\)-complete, this is tight for Pareto-optimal algorithms for P. Proof By Theorems 3 and 7, the theorem holds for \(\textsc{ASG}_{t}\). Thus, by Observation 13, it also holds for any problems in \(\mathcal {C}_{\eta _0,\eta _1}^{t}\). \(\square \) Note that by Proposition 17, all of the problems in \(\mathcal {C}_{\mu _0,\mu _1}^{t}\) have a \((1,t-1,1)\)-competitive algorithm, so there are algorithms with consistency 1. Moreover, problems in the class indexed by t have a t-robust algorithm, and for complete problems this is tight. In introducing some initial complexity classes to the field of online algorithms (with and without predictions), we define reductions from complete problems for each class to all members of the class. The reductions map algorithms for one problem to algorithms for another problem. To show inclusion of a problem P in a class, the map is from P to a complete problem. The original complete problems for each class have binary outputs and predictions. In contrast, the Paging problem, with discard predictions for whether or not the current page will be in a selected \(\textsc{Opt}\)’s cache the next time it is requested, obtains an optimal solution by choosing pages to evict among those that would not be in \(\textsc{Opt}\)’s cache. Thus, the predictions are an encoding of all optimal solutions that would have a page in cache, if the selected \(\textsc{Opt}\) would. The sequence of pages chosen for eviction is the output. 4.3 Establishing the Hierarchy In this subsection, we show that our complexity classes form a strict hierarchy by showing that \(\textsc{ASG}_{t+1}\) is strictly harder than \(\textsc{ASG}_{t}\), for any \(t \in \mathbb {Z}^+\). Lemma 18 For any \(t \in \mathbb {Z}^+\) and any pair of error measures, \((\eta _0,\eta _1)\), - (i) \(\textsc{ASG}_{t+1} \ge _{\text {o}} \textsc{ASG}_{t}\), and - (ii) \(\textsc{ASG}_{t}\) is not as hard as \(\textsc{ASG}_{t+1}\). Proof We prove each item separately. - Towards: - (i): We give a reduction, \(\rho = ({\rho }_{\textsc{a}},{\rho }_{\textsc{i}})\), from \(\textsc{ASG}_{t}\) to \(\textsc{ASG}_{t+1}\). For any \(I=(x,\hat{x},r) \in \mathcal {{I}}_{\textsc{ASG}_{t}}\) and \(\textsc{Alg}_{t+1} \in \mathcal {A}_{\textsc{ASG}_{t+1}}\), we let \({\rho }_{\textsc{i}}(\textsc{Alg}_{t+1}, I) = I\). We let \(\textsc{Alg}_{t} = {\rho }_{\textsc{a}}(\textsc{Alg}_{t+1})\) be the algorithm which, for each request, passes the prediction bit on to \(\textsc{Alg}_{t+1}\) and outputs the same bit as \(\textsc{Alg}_{t+1}\). We verify that this reduction satisfies Conditions (O1)–(O3) from Definition 8. Since \({\rho }_{\textsc{i}}(\textsc{Alg}_{t+1},I) = I\), Conditions (O2)–(O3) are immediate for any pair of error measures \((\eta _0,\eta _1)\). Towards Condition (O1), denote by \(y_1,y_2,\ldots ,y_n\) the bits guessed by \(\textsc{Alg}_{t+1}\), and therefore also by \(\textsc{Alg}_t\). Then, $$\begin{aligned} \textsc{Alg}_{t+1}(I) - \textsc{Alg}_t(I) =&\sum _{i=1}^n \left( y_i + (t+1) \cdot (1-y_i) \cdot x_i\right) \\&- \sum _{i=1}^n \left( y_i + t\cdot (1-y_i) \cdot x_i\right) \\ =&\sum _{i=1}^n (1-y_i) \cdot x_i \geqslant 0, \end{aligned}$$and Condition (O1) follows. - Towards: - (ii): Assume towards contradiction that \(\textsc{ASG}_{t} \ge _{\text {o}} \textsc{ASG}_{t+1}\). Then, for any \((\alpha ,\beta ,\gamma )\)-competitive algorithm for \(\textsc{ASG}_{t}\), there exists an \((\alpha ,\beta ,\gamma )\)-competitive algorithm for \(\textsc{ASG}_{t+1}\). By Theorem 2(i), the algorithm that always guesses 0 is (t, 0, 0)-competitive for \(\textsc{ASG}_{t}\). Hence, there exists a (t, 0, 0)-competitive algorithm for \(\textsc{ASG}_{t+1}\), which contradicts Theorem 2(ii). \(\square \) Lemma 19 For any \(t \in \mathbb {Z}^+\) and any pair of error measures, \((\eta _0,\eta _1)\), \(\mathcal {C}_{\eta _0,\eta _1}^{t} \subsetneq \mathcal {C}_{\eta _0,\eta _1}^{t+1}\). Proof We first prove that \(\mathcal {C}_{\eta _0,\eta _1}^{t} \subseteq \mathcal {C}_{\eta _0,\eta _1}^{t+1}\). For any \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t}\), \(\textsc{ASG}_{t} \ge _{\text {o}} P\), and, by Lemma 18(i), \(\textsc{ASG}_{t+1} \ge _{\text {o}} \textsc{ASG}_{t}\). Thus, by transitivity (Lemma 10), \(\textsc{ASG}_{t+1} \ge _{\text {o}} P\), and so \(P \in \mathcal {C}_{\eta _0,\eta _1}^{t+1}\). To see that \(\mathcal {C}_{\eta _0,\eta _1}^{t} \subsetneq \mathcal {C}_{\eta _0,\eta _1}^{t+1}\), observe that \(\textsc{ASG}_{t+1} \in \mathcal {C}_{\eta _0,\eta _1}^{t+1}\) and, by Lemma 18(ii), \(\textsc{ASG}_{t+1} \not \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). \(\square \) Lemma 20 For any \(t \in \mathbb {Z}^+\) and any pair of error measures, \((\eta _0,\eta _1)\), no \(\mathcal {C}_{\eta _0,\eta _1}^{t+1}\)-hard problem is in \(\mathcal {C}_{\eta _0,\eta _1}^{t}\). Proof Assume towards contradiction that \(\mathcal {C}_{\eta _0,\eta _1}^{t}\) contains a \(\mathcal {C}_{\eta _0,\eta _1}^{t+1}\)-hard problem, P. Then, \(\textsc{ASG}_{t} \ge _{\text {o}} P\), and \(P \ge _{\text {o}} \textsc{ASG}_{t+1}\). Thus, due to transitivity, \(\textsc{ASG}_{t} \ge _{\text {o}} \textsc{ASG}_{t+1}\), contradicting Lemma 18. \(\square \) By similar arguments, we get the following: Lemma 21 For any \(t \in \mathbb {Z}^+\) and any pair of error measures, \((\eta _0,\eta _1)\), - \(\mathcal {C}_{\eta _0,\eta _1}^{t} \subsetneq \mathcal {C}_{\eta _0,\eta _1}\), and - \(\mathcal {C}_{\eta _0,\eta _1}^{t}\) contains no \(\mathcal {C}_{\eta _0,\eta _1}\)-hard problems. Theorem 22 For any pair of error measures \((\eta _0,\eta _1)\), we have a strict hierarchy of complexity classes: 4.4 Purely Online Algorithms Observe that our complexity theory extends to a complexity theory for purely online algorithms as well. In particular, one may consider the complexity classes, \(\mathcal {C}_{Z_0,Z_1}^{t}\). Recall that \(Z_0(I) = Z_1(I) = 0\), for any instance \(I = (x,\hat{x},r)\). In this framework, any \((\alpha ,\beta ,\gamma )\)-competitive algorithm, \(\textsc{Alg}\), for an online minimization problem P, satisfies that for all instances \(I \in \mathcal {{I}}_{P}\), and so \(\textsc{Alg}\) is an \(\alpha \)-competitive purely online algorithm for P. Since \(\textsc{ASG}_{t}\) has a t-competitive algorithm (it guesses all 0s) and is as hard as all problems in \(\mathcal {C}_{Z_0,Z_1}^{t}\), all problems in \(\mathcal {C}_{Z_0,Z_1}^{t}\) are (at worst) t-competitive. By the above and Theorem 14, if a purely online problem, P, has an \(\alpha \)-competitive algorithm, it is in \(\mathcal {C}_{Z_0,Z_1}^{t}\), for any \(t \geqslant \alpha \). If, in addition, P has no \((t-\varepsilon )\)-competitive algorithm, P is \(\mathcal {C}_{Z_0,Z_1}^{t}\)-complete. Since most results in this paper hold for any insertion monotone error measure, and \(Z_0\) and \(Z_1\) are insertion monotone, we obtain a similar complexity theory for purely online algorithms. Observation 23 All results in this paper on problems and complexity classes with respect to insertion monotone error measures also hold for the same problems and classes without predictions. Note that our complexity theory may help translating results for one purely online problem directly to other purely online problems. In Section 7.1.1, we discuss a strategy for proving lower bounds for all \(\mathcal {C}_{\mu _0,\mu _1}^{t}\)-hard problems. Using the same strategy, the lower bound from Theorem 2(ii) on the competitive ratio of any purely online algorithm for \(\textsc{ASG}_{t}\) extends to a lower bound on the competitiveness of any purely online algorithm for any \(\mathcal {C}_{Z_0,Z_1}^{t}\)-hard problems. Observation 24 Assume that some minimization problem, Q, is as hard as some minimization problem, P, with respect to any pair of insertion monotone error measures. Then any lower bound on the competitiveness of the purely online version of P is a lower bound on the competitiveness of the purely online version of Q. Similarly, any upper bound for the purely online version of Q is an upper bound for the purely online version of P. 5 A Template for Online Reductions via Simulation In this section, we introduce a template for creating online reductions from \(\textsc{ASG}_{t}\) to a problem, Q, implying \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hardness of Q with respect to any pair of insertion monotone error measures. Recall from Definition 5 that an error measure is insertion monotone if insertion of a finite number of correctly predicted bits into an instance does not increase the error. The reduction strategy is outlined in Algorithm 1. It might be an advantage to read this template in conjunction with the first example of its use for Vertex Cover (Lemma 25 in Section 6.1) to better understand how elements from the concrete problems enter into the template. Algorithm 1 is a template where the challenge requests and the blocks need to be defined when a concrete online reduction is created. For each request, \(r_i\), of the \(\textsc{ASG}_{t}\) instance, we create and give a challenge request, \(c_i\), to the algorithm, \(\textsc{Alg}'\), for Q in a way such that no information about the true bit, \(x_i'\), can be inferred from the information about the instance obtained so far. If, for instance, Q is \(\textsc{VC}_{t}\), each challenge request will be a vertex which is isolated at arrival. After we have treated the entire \(\textsc{ASG}_{t}\) instance, we give \(\textsc{Alg}'\) one (possibly empty) block of requests per challenge request. For \(\textsc{VC}_{t}\), the ith block consists of a (possibly empty) set of neighbors of the ith challenge request, which an optimal algorithm can reject. The purpose of the blocks is to ensure that \(x'_i=x_i\), for \(1 \leqslant i \leqslant n\), and \(x'_i=0\), for \(i>n\), encode an optimal solution for Q. Thus, for each incorrect bit, \(\hat{x}_i'\), in \(\hat{x}'\), the bit \(\hat{x}_i\) is also incorrect, though \(\hat{x}'\) has additional, correct, predictions associated with the blocks. Since the error measures, \(\eta _0\) and \(\eta _1\), are insertion monotone, \(\eta _0(I')\leqslant \eta _0(I)\) and \(\eta _1(I')\leqslant \eta _1(I)\). Summing up, in the input created for \(\textsc{Alg}'\), the requests are the challenge requests given in Line 2 followed by the block requests (Lines 5–7), the prediction consists of the prediction bits for the \(\textsc{ASG}_{t}\) instance (Line 2) followed by a 0 for each block request, and the optimal solution is the correct solution to the \(\textsc{ASG}_{t}\) instance (Line 4) followed by a 0 for each block request. On each request, \(r_i\), \(\textsc{Alg}\) outputs the same as \(\textsc{Alg}'\) does on \(c_i\). Note that \(\textsc{Alg}'\) may not recognize when the challenge requests end and the blocks begin, in which case it may not answer all of the challenges in the blocks correctly, despite the correct predictions. However, this is not a problem, since the idea is to prove that \(\textsc{Alg}\) does no worse than \(\textsc{Alg}'\). In the online reductions, we need to know which request we are dealing with to create the right blocks. However, most often this is clear from the context, and then we leave out the third parameter to \(B_{Q}(x_j,y_j',j)\). 6 Examples of \(\varvec{\mathcal {C}_{\eta _0,\eta _1}^{t}}\)-Hard Problems We use the reduction template from Section 5 for proving \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hardness of Vertex Cover (Lemma 25), k-Spill (Theorem 33), and Interval Rejection (Lemma 30). In addition, we demonstrate the use of transitivity to prove hardness, creating reductions from Interval Rejection to 2-SAT-Deletion (Theorem 34) and from Vertex Cover to Dominating Set (Theorem 39). 6.1 Vertex Cover Given a graph, \(G = (V,E)\), an algorithm for Vertex Cover finds a subset \(V' \subseteq V\) of vertices such that for each edge \(e = (u,v) \in E\), \(u \in V'\) or \(v \in V'\). The cost of the solution is given by the size of \(V'\), and the goal is to minimize this cost. In t-Bounded Degree Vertex Cover, all vertices have degree at most t. Other work on Vertex Cover includes the following. In the purely online setting, there exists a t-competitive algorithm for t-Bounded Degree Vertex Cover, and the problem does not allow for a \((t-\varepsilon )\)-competitive algorithm, for any \(\varepsilon > 0\) [24]. Considering advice, the problem is AOC-complete [17]. In the offline setting, Vertex Cover is NP-complete [33] and APX-complete [25, 41], and t-Bounded Degree Vertex Cover is MAX-SNP-hard [40]. We formally define the Vertex Cover problem studied in this section: Definition 10 The input to Online t-Bounded Degree Vertex Cover with Predictions (\(\textsc{VC}_{t}\)) is a graph, \(G = (V,E)\), with maximum degree at most t. When an algorithm, \(\textsc{Alg}\), receives a vertex, \(v_i\), it outputs \(y_i = 1\) to accept this vertex or \(y_i = 0\) to reject it. For the algorithm’s solution to be feasible, it must be a vertex cover, i.e., For an instance, \(I = (x,\hat{x},r) \in \mathcal {{I}}_{\textsc{VC}_{t}}\), The set \(\{v_i \mid x_i=1\}\) is an optimal vertex cover. The standard unbounded Online Vertex Cover with Predictions is also considered, and is abbreviated \(\textsc{VC}\). First, we show hardness results for \(\textsc{VC}_{t}\): Lemma 25 For any \(t \in \mathbb {Z}^+\) and any pair of insertion monotone error measures, \((\eta _0,\eta _1)\), \(\textsc{VC}_{t}\) is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard. Proof We give a strict online reduction \(\rho = ({\rho }_{\textsc{a}},{\rho }_{\textsc{i}})\) from \(\textsc{ASG}_{t}\) to \(\textsc{VC}_{t}\), using the reduction template of Algorithm 1 in Section 5 (see Fig. 2 for an example). Consider any \(I = (x,\hat{x},r) \in \mathcal {{I}}_{\textsc{ASG}_{t}}\) and any \(\textsc{Alg}' \in \mathcal {A}_{\textsc{VC}_{t}}\). Let \(\textsc{Alg}= {\rho }_{\textsc{a}}(\textsc{Alg}')\) and \(I'={\rho }_{\textsc{i}}(\textsc{Alg}',I)\) be the \(\textsc{ASG}_{t}\) algorithm and \(\textsc{VC}_{t}\) instance created in the reduction described below. The ith challenge request is an isolated vertex, \(v_i\). Clearly, \(v_1, v_2, \ldots , v_i\) give no information about \(x_i\), as required. Recall from the template that \(\hat{x}_i' = \hat{x}_i\) and that \(\textsc{Alg}\) outputs \(y_i=y'_i\), where \(y_i'\) is the output of \(\textsc{Alg}'\) for \(v_i\). Following all the n challenge requests, we give the n blocks, where the ith block, \(B(x_i,y_i')\), is constructed as follows, with all prediction bits equal to 0 as described in the template. - If \(x_i = 0\), then \(B(x_i,y_i')\) is empty. Thus, no optimal solution will contain \(v_i\). - If \(x_i = y_i' = 1\), then \(B(x_i,y_i')\) contains one request to a vertex, \(v_{i,1}\), connected to \(v_i\), ensuring that there is an optimal solution containing \(v_i\). - If \(x_i = 1\) and \(y_i' = 0\), then \(B(x_i,y_i')\) contains requests to t new vertices, \(v_{i,j}\), \(j=1,2,\ldots ,t\), each connected to \(v_i\), giving \(\textsc{Alg}'\) a cost of t and ensuring that there is an optimal solution containing \(v_i\). Observe that \(\{ v_i \mid x_i=1 \}\) is an optimal solution to the \(\textsc{VC}_{t}\) instance constructed, as required by the template. This shows that \(\textsc{Opt}(I)=\textsc{Opt}(I')\), satisfying Condition (O2) of Definition 8. It also shows that all block requests are correctly predicted, since all block predictions are zero. Since \(\hat{x}'_i=\hat{x}_i\), for each challenge request, \(v_i\), and \(\eta _0\) and \(\eta _1\) are insertion monotone, we conclude that \(\eta _0(I') \leqslant \eta _0(I)\) and \(\eta _1(I') \leqslant \eta _1(I)\), satisfying Condition (O3) of Definition 8. To prove that Condition (O1) is also satisfied, we argue that \(\textsc{Alg}(I)\leqslant \textsc{Alg}'(I')\). For each request, \(r_i\) in r, such that \(x_i = 0\), \(\textsc{Alg}\) and \(\textsc{Alg}'\) both have a cost of \(y_i = y_i'\) on \(r_i\). If \(x_i = y_i' = 1\), both algorithms have a cost of 1 on \(r_i\). Finally, if \(x_i = 1\) and \(y_i' = 0\), then \(\textsc{Alg}\) has a cost of t on \(r_i\) and \(\textsc{Alg}'\) has a cost of t on \(B(x_i,y_i')\). \(\square \) A star graph is a tree where all vertices, except at most one, are leaves. A star forest is a disjoint collection of star graphs. Since the graphs constructed in the proof of Lemma 25 are star forests, we obtain the following corollary. Corollary 26 For any \(t\in \mathbb {Z}^+\) and any pair of insertion monotone error measures, \((\eta _0,\eta _1)\), \(\textsc{VC}_{t}\) is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, even on star forests. Since star forests are interval graphs, we also obtain the following. Corollary 27 For any \(t\in \mathbb {Z}^+\) and any pair of insertion monotone error measures, \((\eta _0,\eta _1)\), \(\textsc{VC}_{t}\) is \(\mathcal {C}_{\eta _0,\eta _1}^{t}\)-hard, even on interval graphs. Note that Fig. 2 is an (interval) graph representation of the intervals in Fig. 3. Now, we turn to showing membership by reducing to \(\textsc{ASG}_{t}\). Lemma 28 For any \(t \in \mathbb {Z}^+\) and any pair of error measures, \((\eta _0,\eta _1)\), \(\textsc{VC}_{t} \in \mathcal {C}_{\eta _0,\eta _1}^{t}\). Proof We define a strict online reduction, \(\rho :\textsc{VC}_{t} \overset{r}{\rightarrow }\ \textsc{ASG}_{t}\). Consider any \(I = (x,\hat{x},r) \in \mathcal {{I}}_{\textsc{VC}_{t}}\) and any \(\textsc{Alg}' \in \mathcal {A}_{\textsc{ASG}_{t}}\). We define an instance, \(I' =(x',\hat{x}',r') \in \mathcal {{I}}_{\textsc{ASG}_{t}}\), and an algorithm, \(\textsc{Alg}\), for handling I using the output of \(\textsc{Alg}'\) on \(I'\): For each request, \(r_i\) in r, give \(\hat{x}'_i=\hat{x}_i\) to \(\textsc{Alg}'\) and let \(y'_i\) be the output of \(\textsc{Alg}'\). If \(v_i\) has a neighbor among \(v_1,\ldots ,v_{i-1}\) which is not in the vertex cover constructed so far, \(\textsc{Alg}\) outputs \(y_i=1\), ensuring that \(\textsc{Alg}\) always outputs a vertex cover. Otherwise, it outputs \(y_i=y'_i\). After the last request of I, compute an optimal solution, x, for I and present \(x'=x\) to \(\textsc{Alg}'\), in order to finish the instance \(I'\). Since we let \(x'=x\) and \(\hat{x}'=\hat{x}\), Condition (O3) from Definition 8 is trivially satisfied for any pair of error measures. Moreover, since \(x'=x\), \(\textsc{Opt}(I) = \textsc{Opt}(I')\), and so Condition (O2) is also satisfied. Hence, it only remains to check Condition (O1). To this end, we prove that \(\textsc{Alg}(I) \leqslant \textsc{Alg}'(I')\). We consider the cost of \(\textsc{Alg}\) and \(\textsc{Alg}'\) on request \(r_i\): - \(y'_i=y_i=0\): - \(x_i=0\): Both algorithms have a cost of 0. - \(x_i=1\): \(\textsc{Alg}'\) has a cost of t and \(\textsc{Alg}\) has a cost of 0. - - \(y'_i=0\), \(y_i=1\): \(\textsc{Alg}\) has a cost of 1. - \(x_i=0\): \(\textsc{Alg}'\) has a cost of 0. - \(x_i=1\): \(\textsc{Alg}'\) has a cost of t. - - \(y'_i=y_i=1\): Both algorithms have a cost of 1. Note that \(\textsc{Alg}\) has a higher cost than \(\textsc{Alg}'\), only when \(x_i=y'_i=0\) and \(y_i=1\). In this case, the cost of \(\textsc{Alg}\) is exactly one higher than that of \(\textsc{Alg}'\). However, from \(y_i \ne y'_i\), it follows by the definition of \(\textsc{Alg}\) that \(v_i\) has a neighbor, \(v_j\), \(jt\). If \(s\geqslant t+2\), then there are at least two pages among the ones requested in the block that \({\textsc{LFD}}\) does not initially have in cache, so \({\textsc{LFD}}(I_b)\geqslant 2\). Thus, only the case \(s=t+1\) remains. In this case, we let P denote the \(t+1\) pages requested within the block \(I_b\). During the first t faults in \(I_b\), \({\textsc{FbB}}\) is filling up the cache again after flushing. For each of the remaining requests within the block, exactly one of the \(t+1\) pages is outside the cache. We argue that \(I_b\) can be split into two subblocks, \(I_b'\)followed by \(I_b''\), such that each subblock contains requests to all \(t+1\) distinct pages in P. Let r be the first request within the block causing an eviction. At the time r arrives, the cache has been filled and r is a request to the one page in P which is not in cache. Thus, the part of \(I_b\) ending with r contains requests to \(t+1\) distinct pages, so we let \(I_b'\)denote this part of \(I_b\). What remains is to prove that the remaining part, \(I_b''\), of \(I_b\) also contains requests to all \(t+1\) pages in P. Note that none of the pages that are in cache at the beginning of \(I_b''\)have been evicted from cache within \(I_b\). We partition P into two subsets, \(P_0\) and \(P_1\), based on the situation at the beginning of \(I_b''\). The set \(P_0\) consists of the pages whose last request came with a 0-prediction and \(P_1=P \setminus P_0\) consists of those whose last request came with a 1-prediction. Note that by the definition of FbB, the last request, \(r'\), of the block is a fault and when \(r'\) arrives, all pages in cache with a prediction of 1 have been evicted within \(I_b\). Therefore, all pages in \(P_1\) that are in cache at the arrival of \(r'\) have been requested with a 0-prediction or brought into cache within \(I_b''\). If one of the pages in \(P_1\) is the page not in cache, it is the page requested by \(r'\). Thus, all pages in \(P_1\) are requested within \(I_b''\). We now argue that all pages in \(P_0\) must also be requested within \(I_b''\). Since there are no incorrect 0-predictions in \(I_b\) and since any paging algorithm, including \({\textsc{LFD}}\), can have at most t pages in cache at a time, each page in \(P_0\) must be requested before the last page in \(P_1\) has been requested. Since \(I_b'\)and \(I_b''\)each contain requests to \(t+1\) distinct pages, \({\textsc{LFD}}\) must fault at least once in each of the two subblocks. \(\square \) Lemma 48 For \(t\geqslant 5\) and any complete block, \(I_b\), with no incorrect 0-predictions, Proof Let s be the number of distinct pages in the block. Since \(I_b\) is a complete block, \(s>t\). By Proposition 45, the block \(I_b\) ended due to Condition 2. Let d be the number of pages \({\textsc{FbB}}\) faults on twice in the block. Note that for each such page, p, the last request to p before the last fault on p in the block has a prediction of 1. Among the d pages that \({\textsc{FbB}}\) faults on twice, let \(d_{\text {c}}\)(\(d_{\text {w}}\)) be the number of pages, p, where the last request to p before the last fault on p had a correct (incorrect) 1-prediction, and note that \(d=d_{\text {c}}+d_{\text {w}}\). Thus, \({\textsc{FbB}}\) faults at most \(s+d\) times in the block, and \({\textsc{LFD}}\) faults at least \(s-t\) times. An independent lower bound on \({\textsc{LFD}}\) is that it faults at least \(d_{\text {c}}\) times. Thus, \({\textsc{FbB}}\) faults at most \(s+d_{\text {w}}+d_{\text {c}}\leqslant 2{\textsc{LFD}}(I_b) + t + d_{\text {w}}\) times. We now show that for \(t \geqslant 5\) and \(\varepsilon =\frac{1}{3t^2}\), which will conclude our proof. We start by establishing The easier case is \(s=t+1\): So, now we assume that \(s \geqslant t+2\): For \(t\geqslant 5\) and \(\varepsilon =\frac{1}{3t^2}\), since for \(s\geqslant t+2\), the right-hand side is greater than 2.5 and the left-hand side is smaller than 2.5. This is equivalent to Now, Having established (9) for all cases, and adding \(2{\textsc{LFD}}(I_b) + (1-\varepsilon )d_{\text {w}}\) to both sides, we get that This establishes (8) and concludes the proof. \(\square \) We can now establish that \(\textsc{Pag}_{t}\) is not complete for the class \(\mathcal {C}_{\mu _0,\mu _1}^{t}\). Theorem 49 For \(t\geqslant 5\), the \(\textsc{Pag}_{t}\) algorithm, FbB, is \((t-\frac{1}{3t^2}, 2t, 1-\frac{1}{3t^2})\)-competitive. Proof We consider the different types of blocks and show that they are each bounded by except a possible last block, where we need an additive term of 2t. Thus, we can sum up the faults over all blocks to get the result. If block \(I_b\) ends due to Condition 1 where all pages in cache have prediction 0, then there have been at least \(t+1\) different pages requested in the block, and \({\textsc{LFD}}\) cannot have them all in cache. Thus, there was an incorrect 0-prediction and \(\mu _0(I_b) \geqslant 1\). Using Lemma 46, the number of faults by \({\textsc{FbB}}\) in \(I_b\) is bounded by If block \(I_b\) ends due to Condition 2, then, by Lemma 48, the number of faults by \({\textsc{FbB}}\) in \(I_b\) is bounded by For the possible final non-ending block, by Lemma 46, the number of faults by \({\textsc{FbB}}\) in \(I_b\) is bounded by We have seen that for any complete block, the number of faults is bounded by (11). Thus, they can be summed up to give the result, using the 2t term from the last block as an additive constant. \(\square \) Corollary 50 \(\textsc{Pag}_{t}\) is not \(\mathcal {C}_{\mu _0,\mu _1}^{t}\)-hard. Proof Since \(\textsc{ASG}_{t}\) is complete for the class, it follows by Lemma 6 that any algorithm for a \(\mathcal {C}_{\mu _0,\mu _1}^{t}\)-hard problem that has \(\alpha 0\), so taking the infimum over all values results in the same competitive ratios. The results in this paper also hold using a definition of competitivenes that allows for an additive \(o(\textsc{Opt})\) term. Note that our definition of relative hardness also applies to maximization problems. In a very recent follow-up to the arXiv version of our paper, online maximization problems with predictions were considered and several maximization problems shown to be members, hard, and complete for \(\mathcal {C}_{\mu _0,\mu _1}^{t}\) [8]. The most interesting open problem is extending our complexity theory to other kinds of predictions. Placing other online problems with or without predictions into the complexity hierarchy, including determining whether or not \(k\text {-}\textsc{Spill}_{t}\) is contained in any of the complexity classes defined, would also be interesting. Other possible directions for future work include considering randomized algorithms as well as other performance measures, for instance using relative worst order analysis [15, 19, 20] or random order analysis [34] instead of competitive analysis. Data Availability No datasets were generated or analysed during the current study. Materials Availability Not applicable. Code Availability Not applicable. Notes We work with separate error measures for predicted 0s and 1s to allow for more detailed results. Our reductions and structural results would also work if we used only one error measure. For instance, letting \(\eta _{t-1,1}(x,\hat{x}) = (t-1) \cdot \mu _0(x,\hat{x}) + \mu _1(x,\hat{x})\), Theorem 3 implies that \(textsc{FtP}\) is (1, 1)-competitive with respect to \(\eta _{t-1,1}\). However, combining the two error measures into one, we lose some detail such as the trade-offs between \(\alpha \), \(\beta \), and \(\gamma \) given in Theorem 43. Other examples of insertion monotone functions are \(L^p\) norms. Moreover, any linear combination of insertion monotone functions is insertion monotone. The latter happens only if \(\textsc{Alg}'\) creates an infeasible solution, incurring an infinite cost. References Reduction from vertex cover to dominating set. https://cs.stackexchange.com/questions/117567/reduction-from-vertex-cover-to-dominating-set. Accessed 10 Sept 2025 Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Boston, MA, USA (1974) Algorithms with predictions. https://algorithms-with-predictions.github.io/. Accessed 27 Jan 2026 Antoniadis, A., Boyar, J., Eliás, M., Favrholdt, L.M., Hoeksma, R., Larsen, K.S., Polak, A., Simon, B.: Paging with succinct predictions. In: 40th International Conference on Machine Learning (ICML), volume 202, pages 952–968, Philadelphia, PA, USA (2023). PMLR Appel, A.W.: Modern Compiler Implementation in C. Cambridge University Press, New York, NY, USA (1998). Reprinted with corrections, 1999; reissued, 2004 Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg, Germany (1999) Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5(2), 78–101 (1966) Berg, M.: Comparing the hardness of online minimization and maximization problems with predictions. In: Frontiers of Algorithmics (IJTCS-FAW), volume 15828 of Lecture Notes in Computer Science (LNCS), pp. 33–48. Heidelberg, Germany, Springer (2025) Böckenhauer, H.-J., Hromkovič, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theoret. Comput. Sci. 554, 95–108 (2014) Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R., Mömke, T.: Online algorithms with advice: The tape model. Inf. Comput. 254(1), 59–83 (2017) Borodin, A., Boyar, J., Larsen, K.S., Pankratov, D.: Advice complexity of priority algorithms. Theor. Comput. Syst. 64, 593–625 (2020) Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA (1998) Borodin, A., Nielsen, M.N., Rackoff, C.: (incremental) priority algorithms. Algorithmica 37(4), 295–326 (2003) Boyar, J., Eidenbenz, S.J., Favrholdt, L.M., Kotrbčík, M., Larsen, K.S.: Online dominating set. Algorithmica 81(5), 1938–1964 (2019) Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Trans. Algo. 3(2), 22 (24 pages) (2007) Boyar, J., Lene, M., Favrholdt, C., Kudahl, K.S., Larsen, J.W.: Mikkelsen: Online Algorithms with Advice: A Survey. ACM Comput. Surv. 50(2), 19 (34 pages) (2017) Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: The advice complexity of a class of hard online problems. Theor. Comput. Syst. 61, 1128–1177 (2017) Boyar, J., Favrholdt, L.M., Kudahl, C., Mikkelsen, J.W.: Weighted online problems with advice. Theor. Comput. Syst. 62, 1443–1469 (2018) Boyar, J., Favrholdt, L.M., Larsen, K.S.: The Relative Worst Order Ratio Applied to Paging. J. Comput. Syst. Sci. 73(5), 818–843 (2007) Boyar, J., Favrholdt, L.M., Larsen, K.S.: Relative Worst-Order Analysis: A Survey. ACM Comput. Surv. 54(1), 1–21 (2021). Article No. 8 Boyar, J., Larsen, K.S., Pankratov, D.: Advice Complexity of Adaptive Priority Algorithms. Theoret. Comput. Sci. 984, 114318 (31 pages) (2024) Chlebík, M., Chlebíkova, J.: On approximation hardness of the minimum 2SAT-DELETION problem. Discret. Appl. Math. 155(2), 172–179 (2007) Damian, M., Pemmaraju, S.V.: APX-hardness of domination problems in circle graphs. Inf. Process. Lett. 97(6), 231–237 (2006) Demange, M., Vangelis, T.: Paschos. On-line vertex-covering. Theoret. Comput. Sci. 332(1–3), 83–108 (2005) Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005) Dobrev, S., Královič, R., Pardubská, D.: Measuring the problem-relevant information in input. RAIRO - Theoret. Inf. Appl. 43(3), 585–613 (2009) Rodney, G.: Downey and Michael R. Fellows. Parameterized Complexity. Springer, Heidelberg, Germany (1999) Downey, R.G., Fellows, M.R.: Fixed-parameter tractibility and completeness I: Basic results. SIAM J. Comput. 24(4), 873–921 (1995) Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. Theoret. Comput. Sci. 412(24), 2642–2656 (2011) Epstein, L., Levin, A., Woeginger, G.: Graph coloring with rejection. J. Comput. Syst. Sci. 77(2), 439–447 (2011) Henzinger, M., Saha, B., Seybold, M.P., Ye, C.: On the complexity of algorithms with predictions for dynamic graph problems. In: 15th Innovations in Theoretical Computer Science Conference (ITCS), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 62:1–62:25, Dagstuhl, Germany (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hromkovič, J., Královič, R., Královič, R.: Information complexity of online problems. In: 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 6281 of Lecture Notes in Computer Science (LNCS), pp. 24–36, Heidelberg, Germany (2010). Springer Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85–103. Heidelberg, Germany (1972). Plenum Press Kenyon, C.: Best-fit bin-packing with random order. In: 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359–364. Philadelphia, PA, USA (1996). Society for Industrial and Applied Mathematics Kleinberg, J., Tardos, É.: Algorithm Design. Addison-Wesley Longman Publishing, Boston, MA, USA (2005) Komm, D.: An Introduction to Online Computation: Determinism, Randomization. Advice. Texts in Theoretical Computer Science. Springer, Switzerland (2016) Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335–354 (1999) Manber, U.: Introduction to Algorithms - A Creative Approach. Addison-Wesley Longman Publishing, Boston, MA, USA (1989) Mikkelsen, J.W.: Randomization can be as helpful as a glimpse of the future in online computation. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 39:1–39:14. Dagstuhl, Germany (2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Full paper in arXiv:1511.05886 [cs.DS] Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991) Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233–235 (1982) Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985) Acknowledgements The authors were supported in part by the Independent Research Fund Denmark, Natural Sciences, grants DFF-0135-00018B and DFF-4283-00079B and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions. The authors would like to thank the anonymous reviewers for interesting, helpful comments. Funding Open access funding provided by University of Southern Denmark. The authors have no relevant financial or non-financial interests to disclose. Author information Authors and Affiliations Contributions All authors contributed equally to this work. Corresponding author Ethics declarations Ethics approval and consent to participate Not applicable. Conflict of interest/Competing interests Not applicable. Consent for publication All authors consent and consent beyond that is not applicable. Competing interests The authors declare no competing interests. Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. An extended abstract of this paper was published in the 19th International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom (IJTCS-FAW), Track A Best Paper Award, volume 15828 of Lecture Notes in Computer Science, pages 49–63. Springer, 2025. Rights and permissions Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. About this article Cite this article Berg, M., Boyar, J., Favrholdt, L.M. et al. Complexity Classes for Online Problems with and without Predictions. Theory Comput Syst 70, 45 (2026). https://doi.org/10.1007/s00224-026-10285-8 Received: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s00224-026-10285-8