Oracles That Compute Values

DOI10.1137/S0097539793247439MaRDI QIDQ4376168zbMATH OpenOpenAlexFDO

Authors S. Homer, Ogihara, Mitsunori, Alan L. Selman, S. Fenner

Publication date 10 February 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793247439

zbMATH Keywords

Boolean hierarchybounded query classescomplexity classescomputational complexitymultivalued functionsNPMVrelativized computation

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 512846
• Bounded queries to SAT and the Boolean hierarchy
• Functions computable with limited access to NP
• Commutative queries
• scientific article; zbMATH DE number 1332676

Cited in

(9)

• A hierarchy based on output multiplicity
• Minimization and \(\mathbf{NP}\) multifunctions
• On the query complexity of selecting minimal sets for monotone predicates
• Oracles and Advice as Measurements
• scientific article; zbMATH DE number 18631 (Why is no real title available?)
• scientific article; zbMATH DE number 1332676 (Why is no real title available?)
• scientific article; zbMATH DE number 512846 (Why is no real title available?)
• The complexity of computing second solutions
• Nondeterministic functions and the existence of optimal proof systems

This page was built for publication: Oracles That Compute Values

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376168)