0
$\begingroup$

Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$. Does $\mathsf{P} = \mathsf{BPP}$ have any implications for

  1. $\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$
  2. $\mathsf{BPTIME}(t(n))/a(n) \subseteq \mathsf{DTIME}(t'(n))/a'(n)$

where $a(n)$ and $a'(n)$ are some fixed functions, e.g. $a(n) = \log_2(n)$ or even $a(n) = 1$, and $t(n)$ and $t'(n)$ are some time-bound?

Note: If $a'(n) \geq t(n) + a(n)$, then a deterministic TM $\mathcal{A}$ can include as advice the $a(n)$-bit randomness of a randomized TM $\mathcal{R}$ plus $\mathcal{R}$'s $t(n)$-bit advice.

Improve this question
$\endgroup$
5
  • $\begingroup$ $C=D$ trivially implies $C/a(n)=D/a(n)$ for any classes $C$ and $D$ and any function $a(n)$. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2022 at 9:26
  • $\begingroup$ Oh, and I forgot to mention that P = BPP implies $\mathrm{BPTIME}(t(n))\subseteq\mathrm{DTIME}(t(n)^{O(1)})$ for any time-constructible function $t(n)\ge n$ by the obvious padding argument. Thus also $\mathrm{BPTIME}(t(n))/a(n)\subseteq\mathrm{DTIME}(t(n)^{O(1)})/a(n)$. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2022 at 9:54
  • $\begingroup$ @EmilJeřábek Thanks for the response. $\mathsf{P}/a(n)$ is the class of languages that are decidable by poly-time deterministic TMs with advice of length $a(n)$. What would be the analog definition of $C/a(n)$ for general $C$? Maybe this is obvious but I don't see it atm. $\endgroup$
    – Nicholas Brandt
    Nov 28, 2022 at 10:08
  • 1
    $\begingroup$ The class of languages $L$ such that there exists $L'\in C$ and a sequence of advice strings $\{w_n:n\in\mathbb N\}$, $|w_n|\le a(n)$, such that $x\in L\iff(x,w_{|x|})\in L'$. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2022 at 11:12
  • $\begingroup$ Thanks again @EmilJeřábek, that clarifies things. If you write your comment as an answer I can accept it. $\endgroup$
    – Nicholas Brandt
    Nov 28, 2022 at 12:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy