I am a complexity beginner, actually a quantum physicist.

In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of BosonSampling exactly, would result in the collapse of the Polynomial Hierarchy.

If you are not familiar with BosonSampling or any quantum physics at all, do not bother, it won't be necessary for this question: I am interested in one particular aspect of the argument, that I do not understand because of my lack of background: It seems to have to do with the relation of function/search problems and corresponding(?) decision problems.

Specifically, on page 33, in the the proof of Theorem 1, they show that a #$P$-hard problem is also contained $FBPP^{{NP}^{\mathcal{O}}}$ where $\mathcal{O}$ is an oracle to some problem called BosonSampling. From there, they immediately seem to get that $$P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$$

My question is: How? I understand that there is a difference between counting/function problem complexity classes like $\#P$ or $FBPP$ and classes for decision problems. But how to relate the results? In particular, why is it $P^{\#P}$ on the left?

  • $\begingroup$ FBPP is a somewhat nonstandard class. Can you recount its definition? $\endgroup$ – Yuval Filmus Sep 4 '19 at 16:59
  • $\begingroup$ See the definition given in the paper in the first answer below. $\endgroup$ – Marsl Sep 5 '19 at 12:47

I'm not an expert, and I have one blank space in my answer, hope someone might fill it in.

$FBPP$ is the class of search problems $R = (B_x)_{x\in\{0,1\}^*}$ for which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr [y \in B_x] ≥ 1 − \varepsilon$, where the probability is over $A$’s internal randomness.

Suppose that $L$ is a $\# P-$hard problem, and $L \in FBPP^{NP^{\mathcal{O}}}$. Then, $$P^{\# P} \subseteq P^{L} \subseteq P^{FBPP^{NP^{\mathcal{O}}}} \subseteq BPP^{NP^{\mathcal{O}}}$$

The second inclusion is clear. The first inclusion: suppose $L_1 \in P^{\# P}$. It means that there exists some polynomial algorithm $\mathcal{A}$ which makes queries to some functions $f_1, f_2, \ldots$ from $\#P$. By the definition of $\#P-$hard problems, $f_i \in FP^{L}$, where $FP$ is the class of polynomially computed functions $f:\{0,1\}^*\rightarrow \{0,1\}^*$. It means that every $\mathcal{A}$'s query to $f_1, f_2, \ldots$ can be replaced by a polynomial program with (at most polynomial) number of queries to $L$, or simply speaking $\mathcal{A}$ is equivalent to some polynomial program $\mathcal{B}$ with queries to $L$. We've shown $$P^{\#P} \subseteq P^{FP^{L}} = P^L$$ We see that $P^{FP}$ can be replaced by $P$.

The third inclusion: again, the same trick: here $P^{FBPP}$ turns to $BPP$. Suppose $L_2 \in P^{FBPP^{NP^{\mathcal{O}}}}$ and $\mathcal{A}$ is the corresponding algorithm for $L_2$. $\mathcal{A}$ makes at most $p(n)$ queries to the probabilistic polynomial programs $A_1, A_2, \ldots$ which solve some search problems. $\mathcal{A}$ uses randomness, but always gives the right answer. One can supposedly make $A_1, A_2\ldots $ a part of $\mathcal{A}$; the resulting probabilistic polynomial algorithm $B$ with queries to $NP^{\mathcal{O}}$ never errs and belongs to $BPP^{NP^{\mathcal{O}}}$.

The only doubt that I have here is that there might be a polynomial number of queries to different functions $FBPP$, and $\mathcal{B}$ is supposed to know all the algorithms for them. It is widely known that if $\mathcal{C}$ is a complexity class with a complete problem $\mathcal{L}$, then $A^{\mathcal{L}} = A^{C}$ for class $P$. However, $BPP$ doesn't have complete problems, and I'm not sure about $FBPP$.

  • $\begingroup$ Hey, the answer is much appreciated. I get the gist but I am looking at the details. For starters, could you provide me with a link or other reference to the definition of #P-hard problems? $\endgroup$ – Marsl Sep 5 '19 at 9:06
  • $\begingroup$ One of the standard textbooks is Computational complexity by S.Arora, B.Barak; it covers #P-complete problems, and #P-hard problems are almost the same, except they're not necessarily contained in #P. $\endgroup$ – diplodoc Sep 5 '19 at 9:47
  • $\begingroup$ Perfect! this already made me understand the logic behind the first inclusion. looking at the 2nd one now $\endgroup$ – Marsl Sep 5 '19 at 10:27
  • $\begingroup$ Just to make sure, we are on the same page: The logic you apply is this: A polynomial time $P$ machine with access to a $FBPP^{NP^{\mathcal{O}}}$ oracle could just as well run a subroutine corresponding to any problem in $FBPP^{NP^{\mathcal{O}}}$ otherwise solved by the oracle while still retaining polynomial time runtime. Of course, while doing so, the full algorithm becomes probabilistic. Thus, I conclude that $P^{FBPP^{NP^{\mathcal{O}}}} = BPP^{NP^{\mathcal{O}}}$ with equality? $\endgroup$ – Marsl Sep 5 '19 at 12:43
  • $\begingroup$ The full algorithm becomes probabilistic, but it always gives the right answer. There's some special complexity class for this case, but I forgot the name (it's not a very popular class). However, $BPP^{NP^{\mathcal{O}}}$ gives the right answer only with some probability ($\ge 1/3$). So if the reasoning is correct and $P$ machine can somehow run subroutines for any problem in $FBPP$ (with queries to the Oracle solving $NP^{\mathcal{O}}$), then the classes are probably not equal. $\endgroup$ – diplodoc Sep 5 '19 at 13:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.