scientific article; zbMATH DE number 512846

MaRDI QIDQ4281541zbMATH OpenFDO

Authors Steve Homer, Mitsunori Ogiwara, Alan L. Selman, S. Fenner

Publication date 10 March 1994

zbMATH Keywords

complexity classes of partial functionsoraclespolynomial-time computablepolynomial-time reducibilities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Oracles That Compute Values
• Functions computable with limited access to NP
• scientific article; zbMATH DE number 1332676

Cited in

(12)

• A hierarchy based on output multiplicity
• Functions computable with limited access to NP
• Minimization and \(\mathbf{NP}\) multifunctions
• Commutative queries
• On low for speed oracles
• Oracles and Advice as Measurements
• scientific article; zbMATH DE number 4049046 (Why is no real title available?)
• scientific article; zbMATH DE number 1332676 (Why is no real title available?)
• Oracles That Compute Values
• Computations with oracles that measure vanishing quantities
• Computing functions with parallel queries to NP
• Symmetric exponential time requires near-maximum circuit size

This page was built for publication:

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