To prove the equivalence, we have to show that P/poly $\subseteq$ BPP/poly and BPP/poly $\subseteq$ P/poly thus P/poly = BPP/poly.

Since BPP $\subseteq$ P/poly. My thinking is, we can also add poly to both sides to get something like BPP/poly $\subseteq$ (P/poly)/poly to also prove the equivalence. Is that possible?

  • $\begingroup$ Do you know a proof that BPP $\subseteq$ P/poly? Have you tried adapting it along the lines you mention? If so, what happened when you tried? $\endgroup$
    – D.W.
    Apr 15 at 6:50
  • $\begingroup$ BPP $\subseteq$ P/poly from Adleman's theorem. When I think about it, it would make sense that adding the advice to both sides could work but 1. I have not seen an advice added to an advice class and 2. I'm not sure if there's any limitations, faulty reasoning on my side, and why it hasn't been tried before. $\endgroup$
    – rock_lee
    Apr 15 at 7:05
  • $\begingroup$ I'm asking whether you are familiar with the proof of Adleman's theorem, and suggesting you try adapting that proof by applying the idea you mention in your post, and see what happens. Don't just theorize about adding /poly to both sides -- adapt each individual step in the proof of the theorem in a concrete way. $\endgroup$
    – D.W.
    Apr 15 at 7:07
  • $\begingroup$ I guess that's where I'm at. I don't fully understand advice classes, just the basics of what they are and why they are important since I'm new to complexity theorems. I understand BPP and from the conclusion of the theorem, we can use a universally good string r to build a circuit for a deterministic verifier with r as input for the witness. Since I don't intuitively understand the theorem, I find it hard to build upon it. $\endgroup$
    – rock_lee
    Apr 15 at 7:43
  • 1
    $\begingroup$ Your argument is correct: (P/poly)/poly = P/poly. Adding advice twice is the same as adding more advice once. There is no point in going through the proof of Adleman’s theorem here, you can treat the theorem as a black box. $\endgroup$ Apr 15 at 7:58


Your Answer

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

Browse other questions tagged or ask your own question.