# Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?

Sanjeev Arora and Boaz Barak show the following :

$P/poly = \cup_{c,d} DTIME (n^c)/n^d$

where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$ and runs in $O(n^c)$ time. I do follow the proof. But I feel the proof only holds if we assume that $\forall n$ the advice given to any two $n$ length strings $x$ and $y$ is same.

But I am unable to see if the theorem still holds if the above condition if not applicable ?

• The advice always depends only on the input length. – Yuval Filmus Mar 5 '16 at 11:24
• The standard advice model explicitly assumes that the advice is the same for all inputs of the same length. – András Salamon Mar 5 '16 at 12:51

Since $P/Poly$ talks about circuit families for languages (different circuit $C_n$ for length $n$ inputs), it is natural to talk about an advice which is a function of the input's length alone. Different advice for each string will make the class too big. For any $L\subseteq \Sigma^*$, your advice for some $x\in\Sigma ^*$ can be 1 if $x\in L$ and 0 otherwise.