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 and acknowledge that you have read and understand our privacy policy and code of conduct.