---
_id: '27160'
abstract:
- lang: eng
text: "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."
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Dorian
full_name: Rudolph, Dorian
last_name: Rudolph
citation:
ama: 'Gharibian S, Rudolph D. On polynomially many queries to NP or QMA oracles.
In: *13th Innovations in Theoretical Computer Science (ITCS 2022)*. Vol 215.
; 2022:1-27. doi:10.4230/LIPIcs.ITCS.2022.75'
apa: Gharibian, S., & Rudolph, D. (2022). On polynomially many queries to NP
or QMA oracles. *13th Innovations in Theoretical Computer Science (ITCS 2022)*,
*215*(75), 1–27. https://doi.org/10.4230/LIPIcs.ITCS.2022.75
bibtex: '@inproceedings{Gharibian_Rudolph_2022, title={On polynomially many queries
to NP or QMA oracles}, volume={215}, DOI={10.4230/LIPIcs.ITCS.2022.75},
number={75}, booktitle={13th Innovations in Theoretical Computer Science (ITCS
2022)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2022}, pages={1–27}
}'
chicago: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to
NP or QMA Oracles.” In *13th Innovations in Theoretical Computer Science (ITCS
2022)*, 215:1–27, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.75.
ieee: 'S. Gharibian and D. Rudolph, “On polynomially many queries to NP or QMA oracles,”
in *13th Innovations in Theoretical Computer Science (ITCS 2022)*, 2022,
vol. 215, no. 75, pp. 1–27, doi: 10.4230/LIPIcs.ITCS.2022.75.'
mla: Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or
QMA Oracles.” *13th Innovations in Theoretical Computer Science (ITCS 2022)*,
vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75.
short: 'S. Gharibian, D. Rudolph, in: 13th Innovations in Theoretical Computer Science
(ITCS 2022), 2022, pp. 1–27.'
date_created: 2021-11-05T08:08:29Z
date_updated: 2023-02-28T11:07:56Z
department:
- _id: '623'
- _id: '7'
doi: 10.4230/LIPIcs.ITCS.2022.75
intvolume: ' 215'
issue: '75'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15671
oa: '1'
page: 1-27
publication: 13th Innovations in Theoretical Computer Science (ITCS 2022)
status: public
title: On polynomially many queries to NP or QMA oracles
type: conference
user_id: '71541'
volume: 215
year: '2022'
...