$P/poly$ as oracle to itself?

Question

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?

Answer 1

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$.

Answer 2

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.