World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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 ?

###### Answered By : Ariel

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54037

3200 people like this