Let $\mathsf C$ be some class. Let $a : \mathbb N \to \mathbb N$ be some function describing the bit length of advice. Let $C/a := \{L | \exists L' \in \mathsf C \text{ and } \exists (w_n)_{n\in \mathbb N} : |w_n| \leq a(n) \wedge x \in L \iff (x,w_{|x|}) \in L'\}$ be the class $C$ with $a$ bits of advice (attributed to @EmilJeřábek in a comment here).

Consider $\mathsf{DTIME}(2^n)/n$. Subjectively, I feel this should be the class of languages that on input $x \in \{0,1\}^n$ can be decided by some DTM in time $2^n$ given $n$ bits of advice (let's say on an "advice" tape). However, the (non-uniform) DTM that decides a language $L \in \mathsf{DTIME}(2^n)/n$ on inputs of length $n$ may actually take $2^{2n}$ steps. This is because the input to the DTM for $L'$ is actually $x||w \in \{0,1\}^{2n}$ (I guess technically, the input and the advice have to be encoded prefix-free, or there needs to be some delimiter between them. I'll ignore that fact.)

Is there some notion/notation for the class that I described above, i.e., where the advice is not included in the input? For classes like $\mathsf{DTIME}$ one can quite easily defined such a class (by adjusting the runtime bound in the definition); however is there a standard notation? For general classes $\mathsf C$ I'm not sure how to formalize the intuition above, as there is not a priori a notion of runtime.

  • $\begingroup$ I'm not sure that, in the standard definition of advice for classes defined by bounding the running time, then the running time of the machine is measured as a function of the input including the advice. In the book by Arora and Barak, "Computational Complexity: A Modern Approach" (mysmth.net/…) in Definition 6.16 the running time of the machine is bounded by considering the length $n$ of the original input, not that of the input with advice. I don't know if this is consistently done, however. $\endgroup$
    – a3nm
    Mar 15, 2023 at 9:02
  • $\begingroup$ @a3nm Thanks for the reference. I guess there is just no "standard" definition of a class with non-uniform advice and hence the notation is overloaded. So one should be careful with the exact definition used. $\endgroup$ Mar 16, 2023 at 9:02
  • $\begingroup$ Btw: AroraBarak also ignores the issue of the prefix-free encoding of the advice. $\endgroup$ Mar 16, 2023 at 9:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.