Prove that for each arbitrary set of natural numbers $A$ we have:
$$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin (n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \mathbb{N}} DTIME\left(2^{(\log n)^c}\right) $$

I have no idea how to move from probablistic machines to non-probablisitic machine. Any ideas ?

Let us note, that $DTIME(n)\subseteq QP$, because for $c=1$ we have $2^{\log n}=n$. Now we use the fact that $BPP\subset EXP$. Let $X=\{bin(n)|n\in A\}$ will be decided by exponetnial turing machine $M$.

Now, we give machine $N$ which in $DTIME(n)$ (so in particular in $QP$) recognize $Y=\{0^n | n\in A\}$.
The $N$ works in following way:
1. Convert unary ($n$ bits) number to binary number ($\log n$) bits.
2. Launch $M$ on this converted input - it takes $2^{\log n}=n$ steps.
3. $n\in DTIME(n)\subseteq QP$.

  • 1
    $\begingroup$ Can you put $BPP$ in $EXP$? Can you think of how does this help you here? $\endgroup$ – Ariel Aug 15 '17 at 14:59
  • $\begingroup$ @Ariel I edited and added my thoughts. I think that it does work, however I am not sure why $BPP\subset EXP$. Can you check my thoughts and clarify $BPP\subset EXP$ ? $\endgroup$ – Haskell Fun Aug 15 '17 at 17:24
  • 1
    $\begingroup$ $EXP=\bigcup\limits_{c} 2^{n^c}$, so $M$ might run in $2^{n^c}$ time, and thus your solution puts $Y$ in $QP$ rather than in linear time. $\endgroup$ – Ariel Aug 15 '17 at 19:24
  • $\begingroup$ Ahhh, ok. Sol solution is almost ok. What about $BPP\subset EXP$ ? $\endgroup$ – Haskell Fun Aug 15 '17 at 20:09
  • 1
    $\begingroup$ @JamesHollis, QP has nothing with quantumness, it means quasipolynomial. $\endgroup$ – rus9384 Aug 15 '17 at 20:35

Your Answer

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

Browse other questions tagged or ask your own question.