Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ADMISSIBLE WEIGHTING FUNCTION:
Reports tagged with admissible weighting function:
TR21-149 | 5th November 2021
Sevag Gharibian, Dorian Rudolph

On polynomially many queries to NP or QMA oracles

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively.
The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate ... more >>>




ISSN 1433-8092 | Imprint