Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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 ?

Asked By : sashas
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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback