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 ?

  • $\begingroup$ The advice always depends only on the input length. $\endgroup$ – Yuval Filmus Mar 5 '16 at 11:24
  • $\begingroup$ The standard advice model explicitly assumes that the advice is the same for all inputs of the same length. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.