1
$\begingroup$

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 ?

Improve this question
$\endgroup$
2
  • $\begingroup$ The advice always depends only on the input length. $\endgroup$
    – Yuval Filmus
    Mar 5, 2016 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, 2016 at 12:51

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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