<p>Let <span class="math-container">$\mathsf C$</span> be some class.
Let <span class="math-container">$a : \mathbb N \to \mathbb N$</span> be some function describing the bit length of advice.
Let <span class="math-container">$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'\}$</span> be the class <span class="math-container">$C$</span> with <span class="math-container">$a$</span> bits of advice
(attributed to @EmilJeřábek in a comment <a href="https://cstheory.stackexchange.com/questions/52201/non-uniform-consequences-of-uniform-derandomization">here</a>).</p>
<p>Consider <span class="math-container">$\mathsf{DTIME}(2^n)/n$</span>.
Subjectively, I feel this should be the class of languages that on input <span class="math-container">$x \in \{0,1\}^n$</span> can be decided by some DTM in time <span class="math-container">$2^n$</span> given <span class="math-container">$n$</span> bits of advice (let's say on an &quot;advice&quot; tape).
However, the (non-uniform) DTM that decides a language <span class="math-container">$L \in \mathsf{DTIME}(2^n)/n$</span> on inputs of length <span class="math-container">$n$</span> may actually take <span class="math-container">$2^{2n}$</span> steps.
This is because the input to the DTM for <span class="math-container">$L'$</span> is actually <span class="math-container">$x||w \in \{0,1\}^{2n}$</span> (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.)</p>
<p>Is there some notion/notation for the class that I described above, i.e., where the advice is <strong>not</strong> included in the input?
For classes like <span class="math-container">$\mathsf{DTIME}$</span> 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 <span class="math-container">$\mathsf C$</span> I'm not sure how to formalize the intuition above, as there is not a priori a notion of runtime.</p>

CC BY-SA 4.0
2023-03-15T09:02:50.220Z
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" (https://www.mysmth.net/bbsanc.php?path=%2Fgroups%2Fcomp.faq%2FAlgorithm%2FNetResources%2FM.1244767166.F0&ap=270) 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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-03-16T09:02:10.330Z
@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.
Nicholas Brandt
CC BY-SA 4.0
2023-03-16T09:06:28.263Z
Btw: AroraBarak also ignores the issue of the prefix-free encoding of the advice.
Nicholas Brandt
<advice-and-nonuniformity>
Non-uniform advice skews runtime
Nicholas Brandt
# Non-uniform advice skews runtime

(Asked by: username_0 on 2023-03-14)

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](https://cstheory.stackexchange.com/questions/52201/non-uniform-consequences-of-uniform-derandomization)).

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.

**Tags:** advice-and-nonuniformity

> **Comments:**
> **username_1**: 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" (https://www.mysmth.net/bbsanc.php?path=%2Fgroups%2Fcomp.faq%2FAlgorithm%2FNetResources%2FM.1244767166.F0&ap=270) 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.  
> **username_0**: @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.  
> **username_0**: Btw: AroraBarak also ignores the issue of the prefix-free encoding of the advice.  

---

## 0 answers

