1
$\begingroup$

How can we show $P/poly^{P/poly}=P/poly$?

What tricks are generally used for self lowness of a class such as $BPP$, $SPP$ etc?

$\endgroup$
1
$\begingroup$

There are no general tricks for proving self lowness, note that the classes that you yourself mentioned are very different in nature. Recall that $L\in P/poly$ iff there exists a Turing machine $M(x,y)$, which runs in time polynomial in $|x|$, and an advice sequence $\{\alpha_n\}_{n\in\mathbb{N}}$, such that for all $x\in\Sigma^*$ it holds that:

$x\in L \iff M\left(x,\alpha_{|x|}\right)=1$

$L\in P/poly^{P/Poly}$ if the machine $M$ above can also query membership to some other language $O\in P/Poly$, so there exists a machine $M_O(x,y)$ which satisfies the above conditions with advice sequence $\beta_n$.

To show that $L$ lies in $P/Poly$, the natural approach would be to use $M$ with the same advice sequence $\alpha_n$. The problem arises when $M$ queries its oracle $O$ on some string $s$, what do we do then? Here the natural approach would be to simulate $M_O$ on $s$, but what advice should we feed to $M_O(s,\cdot)$ ? Suppose $M$ runs in time $n^c$, then on a length $n$ input, $M$ can only query its oracle on strings of length $\le n^c$. This leads to the following solution, on length $n$ inputs, your $P/Poly$ machine for $L$ would use the advice $\left(\alpha_n,\beta_0,\beta_1,...,\beta_{n^c}\right)$, and simulate $M$ on the input with advice $\alpha_n$. Whenever $M$ queries the oracle on a string $s$, simulate $M_O(s,\beta_{s})$ to obtain an answer, and continue executing $M$.

$\endgroup$
0
$\begingroup$

It been a while since I studied complexity, so I may be confusing with notations.

Take language in $A^B \in P/poly^{P/poly}$, decided by TM $M$. We know that $B \in P/poly$, and hence theirs exist another TM $M'$ which deciding $B$.

Build a $P/poly$ TM $T$ thats simulates $M$. Whenever $M$ query the oracle on input $(x,a)$, $T$ can simulate $M'$ on $(x,a)$ and return whatever it does, and continue the simulation.

The running time remains polynomial.

$\endgroup$
1
  • 1
    $\begingroup$ You have shown that $P^P = P$, but you completely ignored the non-uniformity of P/poly. $\endgroup$ – Yuval Filmus Jan 12 '18 at 12:23

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.