---
res:
bibo_abstract:
- "We study the complexity of problems solvable in deterministic polynomial time\r\nwith
access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$\r\nand
$P^{QMA}$, respectively. The former allows one to classify problems more\r\nfinely
than the Polynomial-Time Hierarchy (PH), whereas the latter\r\ncharacterizes physically
motivated problems such as Approximate Simulation\r\n(APX-SIM) [Ambainis, CCC
2014]. In this area, a central role has been played by\r\nthe classes $P^{NP[\\log]}$
and $P^{QMA[\\log]}$, defined identically to $P^{NP}$\r\nand $P^{QMA}$, except
that only logarithmically many oracle queries are\r\nallowed. Here, [Gottlob,
FOCS 1993] showed that if the adaptive queries made by\r\na $P^{NP}$ machine have
a \"query graph\" which is a tree, then this computation\r\ncan be simulated in
$P^{NP[\\log]}$.\r\n In this work, we first show that for any verification class\r\n$C\\in\\{NP,MA,QCMA,QMA,QMA(2),NEXP,QMA_{\\exp}\\}$,
any $P^C$ machine with a query\r\ngraph of \"separator number\" $s$ can be simulated
using deterministic time\r\n$\\exp(s\\log n)$ and $s\\log n$ queries to a $C$-oracle.
When $s\\in O(1)$ (which\r\nincludes the case of $O(1)$-treewidth, and thus also
of trees), this gives an\r\nupper bound of $P^{C[\\log]}$, and when $s\\in O(\\log^k(n))$,
this yields bound\r\n$QP^{C[\\log^{k+1}]}$ (QP meaning quasi-polynomial time).
We next show how to\r\ncombine Gottlob's \"admissible-weighting function\" framework
with the\r\n\"flag-qubit\" framework of [Watson, Bausch, Gharibian, 2020], obtaining
a\r\nunified approach for embedding $P^C$ computations directly into APX-SIM\r\ninstances
in a black-box fashion. Finally, we formalize a simple no-go\r\nstatement about
polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear\r\npolynomial $p$
specified via an arithmetic circuit, if one can \"weakly\r\ncompress\" $p$ so
that its optimal value requires $m$ bits to represent, then\r\n$P^{NP}$ can be
decided with only $m$ queries to an NP-oracle.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Dorian
foaf_name: Rudolph, Dorian
foaf_surname: Rudolph
bibo_doi: 10.4230/LIPIcs.ITCS.2022.75
bibo_issue: '75'
bibo_volume: 215
dct_date: 2022^xs_gYear
dct_language: eng
dct_title: On polynomially many queries to NP or QMA oracles@
...