Abstract:
We utilize the framework of counting martingales and resource-bounded counting measures introduced by Hitchcock, Sekoni, and Shafei (2025) to study counting random oracles. An oracle \(A\) is \(\Delta\)-random if no \(\Delta\)-computable martingale succeeds on \(A\). In this paper we consider the “sharp” resource bounds \(\#\mathsf{P}\) and \(\#\mathsf{QP}\) and the “gap” resource bounds \(\mathsf{GapP}\), \(\mathsf{GapQP}\), and \(\mathsf{GapE}\). Here “QP” means quasipolynomial.
We show that \(\mathsf{PH}^A\) is infinite relative to every \(\#\mathsf{QP}\)-random oracle \(A\). We also prove that a \(\#\mathsf{QP}\)-random oracle \(A\) separates the counting classes \(\oplus\mathsf{P}^A\), \(\mathsf{PP}^A\), and \(\mathsf{C}_{=}\mathsf{P}^A\) from each other and from \(\mathsf{PH}^A\) and \(\mathsf{PSPACE}^A\). Furthermore, we show that \(\mathsf{IP}^A \neq \mathsf{PSPACE}^A\) for every \(\#\mathsf{QP}\)-random \(A\).
In the quantum domain, we strengthen a result of Bennett, Bernstein, Brassard, and Vazirani (1997) by proving that \(\mathsf{NTIME}^B(n)\) is not contained in \(\mathsf{BQTIME}^B(o(2^{n/2}))\) relative to \(\mathsf{GapP}\), \(\mathsf{GapQP}\), or \(\mathsf{GapE}\) random oracles depending on how much oracle use is allowed. We also extend results of Aaronson, Ingram, and Kretschmer (2022) to show that \(\Sigma_{k+1}^{\mathsf{P},A}\) is not contained in \(\mathsf{BQP}^{\Sigma_{k}^{\mathsf{P},A}}\) for all \(k \ge 1\), relative to \(\#\mathsf{QP}\)-random oracles \(A\).
We apply Stockmeyer’s approximate counting of \(\#\mathsf{P}\) (1985) to show that separating \(\mathsf{PH}\) with deterministic \(\mathsf{QP}\)-random oracles yields \(\mathsf{P} \neq \mathsf{NP}\). We also address a question of Aaronson et al. about whether \(\mathsf{P} = \mathsf{NP}\) implies that \(\mathsf{BQP}\) is a “small” complexity class, relating the question to approximate counting of \(\mathsf{GapP}\) functions.
Conference version: