The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice complexity, we define the first online complexity class, AOC. The class includes independent set, vertex cover, dominating set, and several others as complete problems. AOC-complete problems are hard, since a single wrong answer by the online algorithm can have devastating consequences. For each of these problems, we show that\(\log \left (1+(c-1)^{c-1}/c^{c}\right )n={\Theta } (n/c)\) bits of advice are necessary and sufficient (up to an additive term of\(O(\log n)\)) to achieve a competitive ratio ofc. The results are obtained by introducing a new string guessing problem related to those of Emek et al. (Theor. Comput. Sci.412(24), 2642–26562011) and Böckenhauer et al. (Theor. Comput. Sci.554, 95–1082014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems, the AOC-complete problems. Previous results of Halldórsson et al. (Theor. Comput. Sci.289(2), 953–9622002) on online independent set, in a related model, imply that the advice complexity of the problem is Θ(n/c). Our results improve on this by providing an exact formula for the higher-order term. For online disjoint path allocation, Böckenhauer et al. (ISAAC2009) gave a lower bound of Ω(n/c) and an upper bound of\(O((n\log c)/c)\) on the advice complexity. We improve on the upper bound by a factor of\(\log c\). For the remaining problems, no bounds on their advice complexity were previously known.

1. The concept of known history for online problems also appears in [19,20] where it is denotedtransparency.

The authors would like to thank Magnus Gausdal Find for helpful discussions.

Authors and Affiliations

1. Department of Mathematics and Computer Science, University of Southern Denmark, 5230, Odense M, Denmark

   Joan Boyar, Lene M. Favrholdt, Christian Kudahl & Jesper W. Mikkelsen

Corresponding author

Correspondence toJoan Boyar.

A preliminary version of this paper appeared in the proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015),Leibniz International Proceedings in Informatics 30: 116-129, 2015.

This work was partially supported by the Villum Foundation and the Danish Council for Independent Research, Natural Sciences.

Appendix: A: Approximation of the Advice Complexity Bounds

In Theorems 3–8, bounds on the advice complexity ofASG were obtained. These bounds are tight up to an additive term of\(O(\log n)\). However, within the proofs, they are all expressed in terms of the minimum size of a certain covering design or a quotient of binomial coefficients. In this appendix, we prove the closed formula estimates for the advice complexity stated in Theorems 3–8 and 11. Again, these estimates are tight up to an additive term of\(O(\log n)\). The key to obtaining the estimates is the estimation of a binomial coefficient using the binary entropy function.

1.1A.1 Approximating the FunctionB(n,c)

Lemma 15

For c>1, it holds that

Proof

We prove the upper bound first. To this end, note that

Using calculus, one may verify that\(\left (1+\frac {(c-1)^{c-1}}{c^{c}}\right )^{c}\) is decreasing inc forc>1. Thus, by continuity, it follows that

For the lower bound, let\(a=e\ln (2)\) and note that

Again, using calculus, one may verify that\(\left (1+\frac {(c-1)^{c-1}}{c^{c}}\right )^{ac}\) is decreasing inc forc>1. It follows that

□

1.2A.2 The Binary Entropy Function

In this section, we give some properties of the binary entropy function that will be used extensively in AppendixAA.4.

Definition 11

Thebinary entropy function\(H:[0,1]\rightarrow [0,1]\) is the function given by

andH(0)=H(1)=0.

Lemma 16 (Lemma 9.2 in27)

For integers m,n such that 0≤m≤n,

Proposition 1

The binary entropy function H(p) has the following properties.

Proof

(H1): Follows from the definition.

(H2): Fors>1,

(H3): Note thatH is smooth for 0<p<1. The derivative\(H^{\prime }(p)\) can be calculated from the definition. The second-order derivative is

which is strictly less than zero for all 0<p<1.

(H4): Fixt>0. The claim follows by showing that the partial derivative of\(sH(\frac {t}{s})\) with respect tos is positive for alls>t.

(H5):H(p) is increasing for\(0\leq p\leq \frac {1}{2}\) and decreasing for\(\frac {1}{2}\leq p\leq 1\). If\(\frac {1}{x}+\frac {1}{n}\leq \frac 12\), then the claim is trivially true (since then the difference is negative). Assume therefore that\(\frac {1}{x}+\frac {1}{n}> \frac 12\). Under this assumption,\(H(\frac {1}{x})\) increases and\(H(\frac {1}{x}+\frac {1}{n})\) decreases asx tends to 2. Thus,\(H(\frac {1}{x})-H(\frac {1}{x}+\frac {1}{n})\) increases asx tends to 2 and, hence,

Inserting into the definition ofH gives

Since (n+2)/(n−2) is decreasing forn ≥ 3, it follows that\(\log ((n+2)/\)\((n-2))\leq \log (5)\). Furthermore,\((n^{2}-4)/(4n^{2})\leq \frac {1}{4}\) for alln ≥ 3, and so\(\frac {1}{2}\log \left ((n^{2}-4)/(4n^{2})\right )+1\leq 0\). We conclude that, for alln ≥ 3,

Combining (3) and (4) proves (H5). □

1.3A.3 Binomial Coefficients

The following proposition is a collection of simple facts about the binomial coefficient that will be used in AppendicesAA.4 andAA.5.

Proposition 2

Let\(a,b,c\in \mathbb {N}\).

Proof

First, we prove(B1):

(B2) follows directly from(B1).

To prove(B3), we calculate the two fractions separately:

□

1.4A.4 Approximating the Advice Complexity Bounds forminASG

The following lemma is used for proving Theorems 3–5.

Lemma 17

For c>1 and n ≥ 3,

and

Proof

We prove the upper and lower bounds separately.Upper bound: Fixn,c. By Lemma 1,

Note that\(1+\ln \left (\begin {array}{c} \lfloor {ct}\rfloor \\ t\end {array}\right )\leq n\)since we consider only ⌊ct⌋<n. This proves (7). Now, taking the logarithm on both sides gives

Above, we have increased ⌊ct⌋ to ⌈ct⌉ in the binomial coefficient (at the price of an additive term of\(\log n\)). This is done since it will later be convenient to use thatct≤⌈ct⌉. Using Lemma 16, we get that

and therefore

Define

Combining (9) and (10) shows that

The functionM is smooth. For any given input lengthn, we can determine the value oft maximizingM(n,t) using calculus. In order to simplify the notation for these calculations, define

and note that

We want to determine those values oft for which\(\frac {d}{dt}M(n,t)=0\):

Note that\(\frac {d^{2}}{dt^{2}}M(n,t)=H^{\prime \prime }(\frac {t}{n})/n<0\) for all values oft, by(H3). Thus,

The value of\(M(n, \frac {n}{x})\) can be calculated as follows:

Combining (11), (13), and (14), we conclude that

Lower Bound: By Lemma 1,

This proves (5). In order to prove (6), first note that by Lemma 15,

Thus, for\(c \geq \frac {n}{2}\), the righthand side of (6) is negative, and hence, the inequality is trivially true.

Assume now that\(c < \frac {n}{2}\). We will determine an integer value oft such that\(\left (\begin {array}{c} n \\ t\end {array}\right )/\left (\begin {array}{c} \lfloor {ct}\rfloor \\ t\end {array}\right )\) becomes sufficiently large. First, we use Lemma 16:

It is possible thatt=⌊ct⌋, but this is fine sinceH(1)=0. Using(H4), we see that

Thus,

Let\(t^{\prime }=\frac {n}{x}\). We know thatM(n,t) attains its maximum value when\(t=t^{\prime }\). Sincec>1, it is clear thatx>c and hence\(t^{\prime }<\frac {n}{c}\). It follows that\(\lfloor {ct^{\prime }}\rfloor <n\). However,\(t^{\prime }\) might not be an integer. In what follows, we will first argue that\(\lfloor {c\lceil {t^{\prime }}\rceil }\rfloor <n\) and then that\(M(n,\lceil {t^{\prime }}\rceil )\) is close to\(M(n,t^{\prime })\). The desired lower bound will then follow by setting\(t=\lceil {t^{\prime }}\rceil \).

Using calculus, it can be verified that, forc>1,x/c is increasing inc. Hence,

Thus,c≤x/2, and hence,

Note that\(\frac {d}{dt}M(n,t)<0\) for\(t>t^{\prime }\), so\(M(n,\lceil {t^{\prime }}\rceil )\geq M(n,t^{\prime }+1)\). Combining this observation with (H2) and (H5), we get that

By choosing\(t=\lceil {t^{\prime }}\rceil \) in the\(\max \), we conclude that

□

The following lemma is used for proving Theorem 10.

Lemma 18

If c is an integer-valued function of n and c>1, it holds that

Proof

Assume thatc is an integer-valued function ofn, thatc>1 and thatct<n. It follows that

Let\(t=\lfloor {\frac {n}{ec}}\rfloor \). Then

Since

this proves the lemma by choosing\(t=\lfloor {\frac {n}{ec}}\rfloor \). □

1.5A.5 Approximating the Advice Complexity Bounds formaxASG

Lemma 20 of this section is used for Theorems 6–8. In proving Lemma 20, the following lemma will be useful.

Lemma 19

For all n,c, it holds that

On the other hand, it also holds that

Proof

Let

In order to prove the upper bound, we show thatf_n,c(⌊u/c⌋) ≥g_n,c(u)/n, for any integeru, 0<u<n. Note that ⌊u/c⌋<u, sincec>1.

By(B1), the second last inequality is actually an equality, unlessu/c is an integer.

In order to prove the lower bound, we will show thatg_n,c(⌈ct⌉) ≥f_n,c(t)/n, for any integert with ⌊ct⌋<n. Note thatt<⌈ct⌉, sincec>1.

□

Lemma 20

Let c>1 and n ≥ 3. It holds that

Furthermore,

Proof

We prove the lower bound first.

We now prove the upper bound.

□

Reprints and permissions